654. Maximum Binary Tree
1. Description
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.
2. Example
Example 1
Input: nums = [3,2,1,6,0,5]
Output: [6,3,5,null,2,0,null,null,1]
Example 2
Input: nums = [3,2,1]
Output: [3,null,2,null,1]
3. Constraints
- 1 <= nums.length <= 1000
- 0 <= nums[i] <= 1000
- All integers in nums are unique.
4. Solutions
Recursive
n = nums.size()
Time complexity: O($n^2$)
Space complexity: O(n)
class Solution {
public:
TreeNode *constructMaximumBinaryTree(const vector<int> &nums) {
return construct_max_tree(nums, 0, nums.size());
}
private:
TreeNode *construct_max_tree(const vector<int> &nums, int left, int right) {
if (left >= right) {
return nullptr;
}
int max_val_idx = left;
for (int i = left; i < right; ++i) {
if (nums[i] > nums[max_val_idx]) {
max_val_idx = i;
}
}
TreeNode *root = new TreeNode(nums[max_val_idx]);
root->left = construct_max_tree(nums, left, max_val_idx);
root->right = construct_max_tree(nums, max_val_idx + 1, right);
return root;
}
};
Monotonic Stack
n = nums.size()
Time complexity: O(n)
Space complexity: O(n)
class Solution {
public:
TreeNode *constructMaximumBinaryTree(const vector<int> &nums) {
vector<TreeNode *> mono_decrease_nodes;
for (int num : nums) {
TreeNode *node = new TreeNode(num);
while (!mono_decrease_nodes.empty() && node->val > mono_decrease_nodes.back()->val) {
node->left = mono_decrease_nodes.back();
mono_decrease_nodes.pop_back();
}
if (!mono_decrease_nodes.empty()) {
mono_decrease_nodes.back()->right = node;
}
mono_decrease_nodes.push_back(node);
}
return mono_decrease_nodes.front();
}
};