JAVA non recursion solution O(n)time no extra space used


  • 0
    W

    Compare root value or root's right value when inserting a new node.

    public TreeNode constructMaximumBinaryTree(int[] nums) {
        if(nums.length == 0) return null;
        TreeNode root = new TreeNode(nums[0]);
        for(int i = 1; i < nums.length; i++){
            TreeNode node = new TreeNode(nums[i]);
            if(nums[i] > root.val){ // make the new node as root
                TreeNode temp = root;
                root = node;
                root.left = temp;
            }else{
               TreeNode right = root;
               while( right.right != null && right.right.val > node.val) right = right.right; // find a right branch is small than the new node
               TreeNode left = right.right;
               right.right = node;
               node.left = left;
            }
        }
        return root;
    }

Log in to reply
 

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