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.
1from typing import List
2class TreeNode:
3 def __init__(self, x):
4 self.val = x
5 self.left = None
6 self.right = None
7
8class Solution:
9 def constructMaximumBinaryTree(self, nums: List[int]) -> TreeNode:
10 if not nums:
11 return None
12 max_idx = nums.index(max(nums))
13 root = TreeNode(nums[max_idx])
14 root.left = self.constructMaximumBinaryTree(nums[:max_idx])
15 root.right = self.constructMaximumBinaryTree(nums[max_idx + 1:])
16 return rootThis Python solution constructs the maximum binary tree using Pyhton lists and recursion. max function is used to determine the maximum element's index, and slicing helps in defining the subarrays for left and right children, thereby recursively constructing the tree 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.
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.