Last updated on February 28th, 2025 at 01:25 pm

Here, we see a Maximum Binary Tree LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Tree

Companies

Microsoft

Level of Question

Medium

Maximum Binary Tree LeetCode Solution

1. Problem Statement

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

Create a root node whose value is the maximum value in nums.
Recursively build the left subtree on the subarray prefix to the left of the maximum value.
Recursively build the right subtree on the subarray suffix to the right of the maximum value.

Return the maximum binary tree built from nums.

Example 1:

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.

Example 2:

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

2. Coding Pattern Used in Solution

The coding pattern used in all the provided implementations is “Tree Construction”. The problem involves constructing a binary tree based on specific rules (maximum binary tree), which is a common tree construction problem.

3. Code Implementation in Different Languages

3.1 Maximum Binary Tree C++

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return constructMaximumBinaryTree(nums,0,nums.size()-1);
    }
    TreeNode* constructMaximumBinaryTree(vector<int>& nums,int start,int end) {
        if(start>end) return nullptr;
        int index=-1;
        int val=-1;
        for(int i=start;i<=end;i++){
            if(nums[i]>val){
                index=i;
                val=nums[i];
            }
        }
        TreeNode* root=new TreeNode(val);
        root->left=constructMaximumBinaryTree(nums,start,index-1);
        root->right=constructMaximumBinaryTree(nums,index+1,end);
        return root;
    }
};

3.2 Maximum Binary Tree Java

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

3.3 Maximum Binary Tree JavaScript

var constructMaximumBinaryTree = function(nums) {
    if (nums.length === 0) return null;
    let max = Math.max(...nums);
    let index = nums.indexOf(max);
    let head = new TreeNode(max);
    head.left = constructMaximumBinaryTree(nums.slice(0, index));
    head.right = constructMaximumBinaryTree(nums.slice(index + 1));
    return head;
};

3.4 Maximum Binary Tree Python

class Solution(object):
    def constructMaximumBinaryTree(self, nums):
        if not nums:
            return None
        stack = []
        for i in nums:
            node = TreeNode(i)
            lastpop = None
            while stack and stack[-1].val < i:
                lastpop = stack.pop()
            node.left = lastpop
            if stack:
                stack[-1].right = node
            stack.append(node)
        return stack[0]

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(n²)	O(n)
Java	O(n)	O(n)
JavaScript	O(n²)	O(n²)
Python	O(n)	O(n)