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

Constraints:

• 1 <= nums.length <= 1000

• 0 <= nums[i] <= 1000

• All integers in nums are unique.

Input: nums = [3,2,1,6,0,5]
Output: [6,3,5,null,2,0,null,null,1]

Explanation: The recursive calls are as follow:
- The largest value in [3,2,1,6,0,5] is 6. Left prefix is [3,2,1] and right suffix is [0,5].
    - The largest value in [3,2,1] is 3. Left prefix is [] and right suffix is [2,1].
        - Empty array, so no child.
        - The largest value in [2,1] is 2. Left prefix is [] and right suffix is [1].
            - Empty array, so no child.
            - Only one element, so child is a node with value 1.
    - The largest value in [0,5] is 5. Left prefix is [0] and right suffix is [].
        - Only one element, so child is a node with value 0.
        - Empty array, so no child.

💡 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)

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 + Recursion                         =
        # ==================================================
        # time  : O(n^2)
        # space : O(n)
        
        self.nums = nums
        return self.construct(0, len(nums))
        
    def construct(self, left: int, right: int) -> TreeNode:
        if left >= right: return None
        
        maxIndex = self.findMax(left, right)
        return TreeNode(self.nums[maxIndex], 
                        self.construct(left, maxIndex),
                        self.construct(maxIndex+1, right))
    
    def findMax(self, left: int, right: int) -> int:
        maxIndex = left
        for i in range(left, right):
            if self.nums[i] > self.nums[maxIndex]:
                maxIndex = i
                
        return maxIndex

🤖 Java

public class Solution {
    /**
     * @time  : O(n^2)
     * @space : O(n)
     */
    
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        /* base case */
        if(nums.length == 0) return null;
        if(nums.length == 1) return new TreeNode(nums[0]);
        
        return construct(nums, 0, nums.length);
    }
    
    public TreeNode construct(int[] nums, int l, int r) {
        if (l >= r) return null;
        
        int max_i = max(nums, l, r);
        TreeNode root = new TreeNode(nums[max_i]);
        root.left = construct(nums, l, max_i);
        root.right = construct(nums, max_i + 1, r);
        return root;
    }
    
    public int max(int[] nums, int l, int r) {
        int max_i = l;
        for (int i = l; i < r; i++) {
            if (nums[max_i] < nums[i])
                max_i = i;
        }
        return max_i;
    }
}