Sponsored
Sponsored
Recursive Division Approach: This approach involves breaking down the problem using recursive calls. We start by identifying the maximum element in the array, which becomes the root of the tree. We then recursively split the array into sub-arrays on the left and right of the maximum element and construct the left and right subtrees respectively. This leverages the divide-and-conquer paradigm.
Time Complexity: O(n^2), where n is the number of elements, due to the repeated search for the maximum element. Space Complexity: O(n) for the recursion stack.
1#include <stdio.h>
2#include <stdlib.h>
3
4struct TreeNode {
5 int val;
6 struct TreeNode *left;
7 struct TreeNode *right;
8};
9
10struct TreeNode* constructMaximumBinaryTree(int* nums, int numsSize) {
11 if (numsSize == 0) return NULL;
12 int maxIdx = 0;
13 for (int i = 1; i < numsSize; i++) {
14 if (nums[i] > nums[maxIdx]) maxIdx = i;
15 }
16 struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
17 root->val = nums[maxIdx];
18 root->left = constructMaximumBinaryTree(nums, maxIdx);
19 root->right = constructMaximumBinaryTree(nums + maxIdx + 1, numsSize - maxIdx - 1);
20 return root;
21}This C implementation uses a recursive function to build the maximum binary tree. The base case checks if the array is empty, returning NULL for the node. It finds the index of the maximum value, which becomes the root node's value, and then recursively builds the left and right subtrees from the elements to the left and right of this value.
Monotonic Stack Approach: This approach involves utilizing a stack to directly simulate the necessary operations required to construct the maximum binary tree without recursion. By pushing and popping elements based on comparisons with the current element, we maintain a monotonic sequence from which the tree is constructed. This method leverages the stack to ensure that nodes are connected efficiently without the overhead of recursive calls.
Time Complexity: O(n), where n is the number of elements, ensured by single pass and stack operations. Space Complexity: O(n) due to stack storage.
1#include <stack>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
stack<TreeNode*> stk;
for (int num : nums) {
TreeNode* current = new TreeNode(num);
while (!stk.empty() && stk.top()->val < num) {
current->left = stk.top();
stk.pop();
}
if (!stk.empty()) {
stk.top()->right = current;
}
stk.push(current);
}
while (stk.size() > 1) stk.pop();
return stk.top();
}Description: In this C++ implementation, a stack is used to efficiently build the tree by managing nodes in a strictly increasing manner. As elements are added, smaller nodes are linked as left children to ensure the maximum tree property and stack operations are used for efficiently updating tree structure.