0654. Maximum Binary Tree

Medium | Tree + Monotonic Stack | 168 ms (99.67%), 14.9 MB (64.90%)

❓ Problem Statement

Source: LeetCode - Maximum Binary Tree GitHub: Solution / Performance

You are given an integer array nums with no duplicates. A maximum binary tree can be built recursively from nums using the following algorithm:

1. Create a root node whose value is the maximum value in nums.

2. Recursively build the left subtree on the subarray prefix to the left of the maximum value.

3. Recursively build the right subtree on the subarray suffix to the right of the maximum value.

Return the maximum binary tree built from nums.

✍🏻 Constraints & Example

💡 Ideas

We could solve this question in two ways:

1. Recursive Solution - Find MAX for left subtree and right subtree

2. Iterative Solution - Use Monotonic Stack

Recursive Solution

We need two functions (1) Helper for constructing a binary tree (2) Find the MAX element using the left and right boundaries.

The helper function recursively calls itself and the termination condition is when left-boundary >= right-boundary.

Iterative Solution Iterate through the input integer array and use stack to record previous nodes

1. current node's value > previous node's value Keep popping from the stack and append the last node to the current node's left

2. current node's value < previous node's value Append the current node to the previous node's right

3. Push current node onto the stack

🤖 Python3 (Monotic Stack)

class Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> TreeNode:
        # (base case)
        if not nums: return None
        if len(nums) == 1: return TreeNode(nums[0])
        
        # ==================================================
        #  Binary Tree + Monotonic Stack                   =
        # ==================================================
        # time  : O(n)
        # space : O(n)
        
        """
        input: [3,2,1,6,0,5]

        stack: [3]          3.left  = None
        stack: [3,2]        2.left  = None, 3.right = 2
        stack: [3,2,1]      1.left  = None, 2.right = 1
        stack: [6]          6.left  = 3
        stack: [6,0]        0.left  = None, 6.right = 0
        stack: [6,5]        5.left  = 0,    6.right = 5
        """
        
        stack = []
        for i in nums:
            node, last = TreeNode(i), None
            
            # (current node's value > previous node's value)
            #  1. pop from stack
            #  2. append the MAX element in the stack to current node's left
            while stack and stack[-1].val < i:
                last = stack.pop()
            node.left = last
            
            # (current node's value < previous node's value)
            # append current node to previous node's right
            if stack: stack[-1].right = node
            
            stack.append(node)
            
        return stack[0]

🤖 Python3 (Recursive)

🤖 Java