Java in-order traversal tree construction using divide and conquer


  • 0
    Y

    This solution is using an in-order traversal to construct the tree. First I find the length of the linked list, and then use divide and conquer method to divide the problem into subproblems. A figure can demonstrate it better. We find the mid index of the linked list, and recursive construct the tree on left and right part. The recursion stops when start is greater than end, and return a null. At the same time, the right node is returned a null as well. The recursion continues to construct the tree.

    divide and conquer

    ListNode current;
    public TreeNode sortedListToBST(ListNode head) {
        current = head;
        int len = getLength(head);
        return helper(0, len-1);
    }
    
    private TreeNode helper(int lo, int hi) {
        if(lo > hi) {
            return null;
        }
        int mid = lo + (hi - lo) / 2;
        TreeNode left = helper(lo, mid-1);
        TreeNode root = new TreeNode(current.val);
        current = current.next;
        TreeNode right = helper(mid+1, hi);
        root.left = left;
        root.right = right;
        return root;
    }
    
    private int getLength(ListNode head) {
        int len = 0;
        while(head != null) {
            head = head.next;
            len++;
        }
        return len;
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.