java O(n) solution with stack


  • 0
    D
    public TreeNode constructMaximumBinaryTree(int[] nums) {
            Stack<TreeNode> stack = new Stack();
            int max = Integer.MIN_VALUE;
            TreeNode root = null;
            for(int each: nums){
                TreeNode n = new TreeNode(each);
                if(max<each){
                    max = each;
                    root = n;
                }
                if(stack.size()==0 ||stack.peek().val>n.val ){
                    stack.add(n);
                }else{
                    TreeNode pop = stack.pop();
                    while(stack.size()>0 && stack.peek().val< n.val){
                        stack.peek().right = pop;
                        pop = stack.pop();
                    }
                    n.left = pop;
                    stack.add(n);
                }
            }
            if(stack.size()>0){
                TreeNode pop = stack.pop();
                while(stack.size()>0 ){
                    stack.peek().right = pop;
                    pop = stack.pop();
                }
            }
            return root;
        }
    

Log in to reply
 

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