Last updated on July 19th, 2024 at 10:23 pm

Here, We see Maximum Binary Tree LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Topics

Tree

Companies

Microsoft

Level of Question

Medium

Maximum Binary Tree LeetCode Solution

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:

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.

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]

1. Maximum Binary Tree LeetCode Solution 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;
    }
};

2. Maximum Binary Tree LeetCode Solution 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. Maximum Binary Tree Solution 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;
};

4. Maximum Binary Tree Solution 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]