Avoiding "finding mid node of a list" by build from bottom


  • 0
    X
    public class Solution {
    public ListNode rootCursor;
    public TreeNode sortedListToBST(ListNode head) {
        ListNode cursor = head;
        int len = 0;
        while(cursor!=null){
            len += 1;
            cursor = cursor.next;
        }
        rootCursor = head;
        return helper(0,len-1);
    }
    public TreeNode helper(int start, int end){
        if(start > end) return null;
        int median = (start+end)/2;
        TreeNode leftChild = helper(start,median-1);
        TreeNode root = new TreeNode(rootCursor.val);
        rootCursor = rootCursor.next;
        root.left = leftChild;
        root.right = helper(median+1,end);
        return root;
    }
    

    }


  • 0
    I

    @xuechao
    thanks
    it is a very nice solution
    but I noticed that, the order is not the same.

    I change a little bit and keep the same order, in js code

    //  start <= x < end
        function helper(start, end){
            if(start >= end) return null;
            var median = ((start + end) / 2) >> 0;
            var leftChild = helper(start, median);
            var root = new TreeNode(rootCursor.val);
            rootCursor = rootCursor.next;
            root.left = leftChild;
            root.right = helper(median+1,end);
            return root;
        }
    
        return helper(0, len);  
    
    

Log in to reply
 

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