Java worst case O(N) solution


  • 8
    S

    Each node went into stack once, and went out stack once. Worst case time complexity O(N).

    class Solution {
        public TreeNode constructMaximumBinaryTree(int[] nums) {
            Deque<TreeNode> stack = new LinkedList<>();
            for(int i = 0; i < nums.length; i++) {
                TreeNode curr = new TreeNode(nums[i]);
                while(!stack.isEmpty() && stack.peek().val < nums[i]) {
                    curr.left = stack.pop();
                }
                if(!stack.isEmpty()) {
                    stack.peek().right = curr;
                }
                stack.push(curr);
            }
            
            return stack.isEmpty() ? null : stack.removeLast();
        }
    }

  • 0
    V

    @SPARC took some time to understand but this solution is really good


  • 0
    Y

    might be better to include some explanation as the implementation is a bit abstract.

    1. traverse the array once and create the node one by one. and use stack to store a decreasing sequence.
    2. each step, we create a new curNode. compare to the peek of stack,
      2.a. keep popping the stack while (stack.peek().val < curNode.val), and set the last popping node to be curNode.left.
      Because the last one fulfilling the criteria is the largest number among curNode's left children. => curNode.left = last pop node
      2.b. after popping up all nodes that fulfill (stack.peek().val < curNode.val),
      thus (stack.peek().val > curNode.val), the stack.peek() is curNode's root => peek.right = curNode
    3. return the bottom node of stack.

    -- reworded from comment by xavier9084 in https://leetcode.com/problems/maximum-binary-tree/solution/


Log in to reply
 

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