Clean Java Solution. O(n) Time


  • 0
    J
    public class Solution {
        public TreeNode sortedListToBST(ListNode head) {
            // corner case
            if (head == null) {
                return null;
            }
            ListNode[] curListNode = new ListNode[]{head};
            // Get the length of the LinkedList
            int len = 0;
            ListNode cur = head;
            while (cur != null) {
                len ++;
                cur = cur.next;
            }
            return buildHelper(curListNode, len);
        }
        private TreeNode buildHelper(ListNode[] curListNode, int len) {
            // base case
            if (len == 0) {
                return null;
            }
            int halfLen = (len - 1) / 2;
            TreeNode leftPart = buildHelper(curListNode, halfLen);
            // At current layer, build the current TreeNode
            TreeNode root = new TreeNode(curListNode[0].val);
            curListNode[0] = curListNode[0].next;
            root.left = leftPart;
            
            TreeNode rightPart = buildHelper(curListNode, len - halfLen - 1);
            root.right = rightPart;
            return root;
        }
    }
    

Log in to reply
 

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