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

Solution: 与array的区别:每次要通过findMid()找到中点(根据start和end),base case: start == end时返回null, start.next == end时返回一个TreeNode

    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) {
            return null;
        }
        return helper(head, null);
    }
    private TreeNode helper(ListNode head, ListNode end) {
        if (head == end) {
            return null;
        }
        if (head.next == end) {
            return new TreeNode(head.val);
        }
        ListNode mid = findMid(head, end);
        TreeNode root = new TreeNode(mid.val);
        root.left = helper(head, mid);
        root.right = helper(mid.next, end);
        return root;
    }
    private ListNode findMid(ListNode head, ListNode end) {
        ListNode slow = head, fast = head.next;
        while (fast != end && fast.next != end) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

results matching ""

    No results matching ""