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 <vector>
2using namespace std;
3
4struct TreeNode {
5 int val;
6 TreeNode *left;
7 TreeNode *right;
8 TreeNode(int x) : val(x), left(NULL), right(NULL) {}
9};
10
11TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
12 if (nums.empty()) return NULL;
13 auto max_it = max_element(nums.begin(), nums.end());
14 TreeNode* root = new TreeNode(*max_it);
15 vector<int> left(nums.begin(), max_it);
16 vector<int> right(max_it + 1, nums.end());
17 root->left = constructMaximumBinaryTree(left);
18 root->right = constructMaximumBinaryTree(right);
19 return root;
20}This C++ solution follows the same recursive strategy as in C. It uses standard library functions to find the maximum element and splits the vector to form the left and right subtrees. The TreeNode class is defined to hold the node value and pointers to left and right children.
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.
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
public TreeNode ConstructMaximumBinaryTree(int[] nums) {
Stack<TreeNode> stack = new Stack<TreeNode>();
foreach (int num in nums) {
TreeNode current = new TreeNode(num);
while (stack.Count > 0 && stack.Peek().val < num) {
current.left = stack.Pop();
}
if (stack.Count > 0) {
stack.Peek().right = current;
}
stack.Push(current);
}
while (stack.Count > 1) stack.Pop();
return stack.Pop();
}
}Description: The C# implementation parallels the Java solution, using a stack to dynamically and efficiently assign children as the array is traversed. It provides a method to ensure elements are removed and linked appropriately to maintain the binary tree's max-heap property.