Algorithm
Problem Name: 654. Maximum Binary Tree
Problem Link: https://leetcode.com/problems/maximum-binary-tree/
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]
Constraints:
1 <= nums.length <= 10000 <= nums[i] <= 1000- All integers in
numsare unique.
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
return DFS(nums, 0, nums.size());
}
TreeNode* DFS(vector<int>& nums, int l, int r){
if(l == r) return NULL;
int maxPos = l;
for(int i = l; i < r; i++> if(nums[i] > nums[maxPos]) maxPos = i;
TreeNode* root = new TreeNode(nums[maxPos]);
root->left = DFS(nums, l, maxPos);
root->right = DFS(nums, maxPos + 1, r);
return root;
}
};
// O(n)
class Solution {
public:
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
deque < TreeNode*>q;
for(auto x: nums){
TreeNode* p = new TreeNode(x);
while(!q.empty() && q.back()->val < x) p->left = q.back(), q.pop_back();
if(!q.empty() && q.back()->val > x) q.back()->right = p;
q.push_back(p);
}
return q.front();
}
};
Input
nums = [3,2,1,6,0,5]
Output
[6,3,5,null,2,0,null,null,1]
#2 Code Example with Java Programming
Code -
Java Programming
class Solution {
public TreeNode constructMaximumBinaryTree(int[] nums) {
if (nums.length == 0) {
return null;
}
TreeNode root = helper(nums, 0, nums.length - 1);
return root;
}
private TreeNode helper(int[] nums, int start, int end) {
if (start > end) {
return null;
}
int maxIdx = getMaxIdx(nums, start, end);
TreeNode root = new TreeNode(nums[maxIdx]);
root.left = helper(nums, start, maxIdx - 1);
root.right = helper(nums, maxIdx + 1, end);
return root;
}
private int getMaxIdx(int[] nums, int start, int end) {
int maxVal = Integer.MIN_VALUE;
int maxIdx = -1;
while (start < = end) {
if (nums[start] > maxVal) {
maxVal = nums[start];
maxIdx = start;
}
start++;
}
return maxIdx;
}
}
Input
nums = [3,2,1,6,0,5]
Output
[6,3,5,null,2,0,null,null,1]
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def constructMaximumBinaryTree(self, nums):
"""
:type nums: List[int]
:rtype: TreeNode
"""
if nums:
pos = nums.index(max(nums))
root = TreeNode(nums[pos])
root.left = self.constructMaximumBinaryTree(nums[:pos])
root.right = self.constructMaximumBinaryTree(nums[pos+1:])
return root
Input
nums = [3,2,1]
Output
[3,null,2,null,1]
#4 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _0654_MaximumBinaryTree
{
public TreeNode ConstructMaximumBinaryTree(int[] nums)
{
return ConstructMaximumBinaryTree(nums, 0, nums.Length);
}
private TreeNode ConstructMaximumBinaryTree(int[] nums, int left, int right)
{
if (left == right) return null;
var maxIndex = GetMaxIndex(nums, left, right);
var node = new TreeNode(nums[maxIndex]);
node.left = ConstructMaximumBinaryTree(nums, left, maxIndex);
node.right = ConstructMaximumBinaryTree(nums, maxIndex + 1, right);
return node;
}
private int GetMaxIndex(int[] nums, int left, int right)
{
var result = left;
for (int i = left; i < right; i++)
if (nums[result] < nums[i]) result = i;
return result;
}
}
}
Input
nums = [3,2,1]
Output
[3,null,2,null,1]