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.
1public class TreeNode {
2 public int val;
3 public TreeNode left;
4 public TreeNode right;
5 public TreeNode(int x) { val = x; }
6}
7
8public class Solution {
9 public TreeNode ConstructMaximumBinaryTree(int[] nums) {
10 return Construct(nums, 0, nums.Length);
11 }
12
13 private TreeNode Construct(int[] nums, int left, int right) {
14 if (left == right) return null;
15 int maxIndex = left;
16 for (int i = left + 1; i < right; i++) {
17 if (nums[i] > nums[maxIndex]) maxIndex = i;
18 }
19 TreeNode root = new TreeNode(nums[maxIndex]);
20 root.left = Construct(nums, left, maxIndex);
21 root.right = Construct(nums, maxIndex + 1, right);
22 return root;
23 }
24}The C# solution employs a recursive method similar to the Java solution. A helper method, Construct, recursively partitions the array similarly, searching for the max index to build left and right subtree nodes.
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.
#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.