JAVA O(N) Solution


  • 0
    B

    The idea is similar to using stack of mids, but I find it cleaner to understand.
    (Key Idea) You can always see a node as a mid and find all its right and append to next node as a left.

    1. Start with left most node
    2. Then you find its right which is exactly the same as building a tree from scratch, but having a limit of this node
    3. Append to next node(new mid) as a left.
    4. Find new mid's right.
    5. Then again you have a left, repeat from step 3 until the end of nums.
    class Solution {
        
        int i = 0;
        
        public TreeNode constructMaximumBinaryTree(int[] nums) {
            i = 0;
            return findRight(nums, Integer.MAX_VALUE);
        }
        
        private TreeNode findRight(int[] nums, int curMax){
            if(i >= nums.length || nums[i] > curMax){
                return null;
            }
            
            TreeNode root = new TreeNode(nums[i]);
            i++;
            while(i < nums.length && nums[i] <= curMax){
                if(nums[i] > root.val){
                    TreeNode t = new TreeNode(nums[i]);
                    t.left = root;
                    root = t;
                    i++;
                }
    
                root.right = findRight(nums, root.val);
            }
            return root;
        }
    }
    

Log in to reply
 

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