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.
1class TreeNode {
2 int val;
3 TreeNode left;
4 TreeNode right;
5 TreeNode(int x) { val = x; }
6}
7
8class Solution {
9 public TreeNode constructMaximumBinaryTree(int[] nums) {
10 return construct(nums, 0, nums.length);
11 }
12 private TreeNode construct(int[] nums, int left, int right) {
13 if (left == right) return null;
14 int maxIndex = left;
15 for (int i = left + 1; i < right; i++) {
16 if (nums[i] > nums[maxIndex]) maxIndex = i;
17 }
18 TreeNode root = new TreeNode(nums[maxIndex]);
19 root.left = construct(nums, left, maxIndex);
20 root.right = construct(nums, maxIndex + 1, right);
21 return root;
22 }
23}In Java, this implementation utilizes a helper method to aid in recursion. The construct function manages the left and right indices within the array to divide the problem space, searching for the maximum and then recursively placing nodes appropriately in the binary tree.
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.