Java solution less than 20 lines!!! Really concise one and easy to understand!


  • 0
    1. Find the middle one to divide & conquer the question
    2. use a helper to set the tree's head & end (the tree should be constructed between head & end - 1)
        public TreeNode sortedListToBST(ListNode head) {
        	return helper(head, null);
        }
        
        public TreeNode helper(ListNode head, ListNode end) { 
            // BST tree from head to end - 1
        	if (head == end) {
        	   return null; 
        	}
        	ListNode mid = head, fast = head; 
        	// mid is the middle point of list from head to end
        	while (fast.next != end && fast.next.next != end) {
        	    mid = mid.next;
        	    fast = fast.next.next;
        	    
        	}
        	TreeNode root = new TreeNode(mid.val);
        	root.left = helper(head, mid);
        	root.right = helper(mid.next, end);
        	return root;
        }
    

Log in to reply
 

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