109. Convert Sorted List to Binary Search Tree

题目描述

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

解题方法

找中點方式

  public TreeNode sortedListToBST(ListNode head) {
        if(head == null){ return null; }
        return toBST(head, null);
    }

    //找範圍
    private TreeNode toBST(ListNode head, ListNode tail){
        if( head == tail ) {return null; }

        ListNode mid = findMiddle(head, tail);

        TreeNode thead = new TreeNode(mid.val);
        thead.left = toBST(head, mid);
        thead.right = toBST(mid.next, tail);
        return thead; //return root
    }

    private ListNode findMiddle(ListNode head, ListNode tail){
        ListNode fast = head.next;
        ListNode slow = head;
        while( fast != tail && fast.next != tail){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }