654. Maximum Binary Tree

This problem asks to construct a maximum binary tree from an integer array. A maximum binary tree is defined recursively:

1. The root is the maximum value in the array.
2. The left subtree is the maximum binary tree constructed from the subarray to the left of the maximum value.
3. The right subtree is the maximum binary tree constructed from the subarray to the right of the maximum value.

We'll explore three approaches to solve this problem: a recursive approach, a segment tree approach, and an iterative approach using a stack.

Solution 1: Recursive Approach

This is the most straightforward approach, directly mirroring the recursive definition of the maximum binary tree.

Algorithm:

1. Find the maximum value in the input array nums and its index.
2. Create a root node with the maximum value.
3. Recursively call the function to build the left subtree using the subarray to the left of the maximum value.
4. Recursively call the function to build the right subtree using the subarray to the right of the maximum value.
5. Return the root node.

Time Complexity: O(N^2), where N is the length of the input array. Finding the maximum in each recursive call takes O(N) time in the worst case. The recursion depth is at most N.

Space Complexity: O(N) in the worst case due to the recursion stack and the implicit space used by the tree.

Code (Python):

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
class Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
        def dfs(nums):
            if not nums:
                return None
            max_val = max(nums)
            max_index = nums.index(max_val)
            root = TreeNode(max_val)
            root.left = dfs(nums[:max_index])
            root.right = dfs(nums[max_index+1:])
            return root
        return dfs(nums)
 

The code in other languages (Java, C++, Go, TypeScript, Rust, C) follows a similar structure, differing only in syntax and data structure implementations.

Solution 2: Segment Tree Approach

This approach uses a segment tree to efficiently find the maximum value in any subarray.

Algorithm:

1. Build a segment tree from the input array. The segment tree allows for O(log N) queries to find the maximum in a given range.
2. Recursively construct the tree:
   • Find the maximum value in the current range using the segment tree.
   • Create a root node with this maximum value.
   • Recursively build the left and right subtrees using the appropriate ranges.

Time Complexity: O(N log N) for building the segment tree, and O(N log N) for constructing the binary tree. The overall time complexity is O(N log N).

Space Complexity: O(N) for the segment tree and O(N) for the recursion stack and the tree itself.

Code (Python):

(The Python code for the Segment Tree solution is provided in the original response.) Similar implementations exist for other languages. Note that this is a significantly more complex solution than the recursive approach and adds considerable overhead. Unless extremely large input arrays are expected, the recursive approach is simpler and arguably faster.

Solution 3: Iterative Approach with Stack

This approach uses a stack to construct the tree iteratively.

Algorithm:

1. Iterate through the input array.
2. For each element v:
   • Create a new node with value v.
   • While the stack is not empty and the top element's value is less than v, pop the top element. The popped elements become the left children of the current node.
   • If the stack is not empty, set the right child of the stack top to the current node.
   • Push the current node onto the stack.

Time Complexity: O(N), as we iterate through the array once.

Space Complexity: O(N) in the worst case, as the stack may contain up to N nodes.

Code (Python):

class Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
        stack = []
        for num in nums:
            node = TreeNode(num)
            while stack and stack[-1].val < num:
                node.left = stack.pop()
            if stack:
                stack[-1].right = node
            stack.append(node)
        return stack[0]
 

Again, the implementation in other languages is very similar.

In Summary:

The recursive solution (Solution 1) is the simplest and easiest to understand. Solution 3 offers a significant improvement in time complexity, making it the most efficient approach for large datasets. Solution 2 is considerably more complex and doesn't offer a significant performance advantage unless dealing with extremely large inputs. Choose the solution that best fits your needs and understanding.