A very simple Java Solution!!!!!!!!! We just need to calculate the middle point.


  • 1
    C
    public TreeNode sortedListToBST(ListNode head) {
    	return sortedListToBST(head, null);
    }
    public TreeNode sortedListToBST(ListNode head, ListNode end) { // BST tree from head to end
    	if (head==end) return null;
    	ListNode slow=head, fast=head; // slow is the middle point of list from head to end
    	while (fast.next!=end && fast.next.next!=end) {slow=slow.next;fast=fast.next.next;}
    	TreeNode root=new TreeNode(slow.val);
    	root.left=sortedListToBST(head, slow);
    	root.right=sortedListToBST(slow.next, end);
    	return root;
    }

  • 0

    I think your solution is great and it is the same idea I tried, but yours is more concise


  • 0
    C

    @ckcz123
    Hi, really like your solution, and i am just wondering why can't I use
    while (fast.next!=null && fast.next.next!=null) in the while loop? why it has to be !=end?
    Aren't they the same? When I use !=null, it just says stack overflow.


  • 0
    C

    @cqy0118
    No, they aren't the same, as we use recursion.
    Take 1->2->3->4->5->null for example, slow=3, and we need to calculate 1->2 in left sub-tree and 4->5 in right sub-tree.
    It's actually 1->2->3, not 1->2->null, and that's why we need to use end instead of null.


  • 0
    C

    @ckcz123 Ok! I got it! Thank you so much!


Log in to reply
 

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