Title Link:/problems/maximum-binary-tree/description/
title narrative
Given a non-repeating array of integers, nums. A maximal binary tree can be constructed recursively from nums using the following algorithm.
Creates a root node whose value is the maximum of nums.
Recursively builds a left subtree on the subarray prefix to the left of the maximum.
Recursively builds a right subtree on the suffix of the subarray to the right of the maximum value.
Returns the largest binary tree constructed by nums.
Example 1:
Input: nums = [3,2,1,6,0,5]
Output: [6,3,5,null,2,0,null,null,1]
Explanation: The recursive call is shown below:
- The maximum value in [3,2,1,6,0,5] is 6, the left part is [3,2,1] and the right part is [0,5].
- The maximum value in [3,2,1] is 3, the left part is [] and the right part is [2,1].
- Empty array with no child nodes.
- The maximum value in [2,1] is 2, the left part is [] and the right part is [1].
- Empty array with no child nodes.
- There is only one element, so the child node is a node with value 1.
- The maximum value in [0,5] is 5, the left part is [0] and the right part is [].
- There is only one element, so a child node is a node with a value of 0.
- Empty array with no child nodes.
- The maximum value in [3,2,1] is 3, the left part is [] and the right part is [2,1].
Example 2:
Input: nums = [3,2,1]
Output: [3,null,2,null,1]
Tip:
1 <= <= 1000
0 <= nums[i] <= 1000
All integers in nums are different from each other.
Thoughts:
Constructing a tree is generally done using a preorder traversal, as the middle node is constructed first, and then the left and right subtrees are constructed recursively.
Let's walk through the three steps of recursion:
-
The parameters and return value of the recursive function: the return value is obviously the node type of the TreeNode, and the parameters we need to pass an array of
-
Recursive end conditions: the title says the input array size must be greater than or equal to 1, so we do not have to consider the case of less than 1, then when the recursive traversal, if the incoming array size of 1, that traversal to the leaf nodes.
Then a new node should be defined and the value of this array should be assigned to the new node and returned. This represents an array size of 1, constructs a new node, and returns it.
TreeNode* node = new TreeNode(0);
if (() == 1) {
node->val = nums[0];
return node;
}
3. recursive single-level logic:
We need to find the maximum value in this array, and then split the array, with the array to the left of the maximum value constructing the left subtree, and the array to the right of the maximum value constructing the right subtree, but before we can do that, we need to find the subscripts that correspond to the maximum value and the maximal value
//finds the largest element in the array and the subscript where the largest element is located
int maxValue = 0;
int index = 0; for (int i = 0; i < (); i++) {
for (int i = 0; i < (); i++) {
if (nums[i] > maxValue) {
index = i; maxValue = nums[i] > maxValue) {
maxValue = nums[i];
}
}
// Assign a value to the root node
node->val = maxValue;
Then there is the process of constructing the left and right subtrees of the root node node, we can use two arrays to store the sequence to the left of the maximum value and the sequence to the right of the maximum value
if (index >= 1) {
// Because the vector's copy constructor is left-open-right-closed logic
vector<int> newVec((), () + index);
node->left = constructMaximumBinaryTree(newVec);
}
// Ensure that the number of elements in the right subtree is ≥ 1
if ((() - 1) - index > 0) {
vector<int> newVec(() + index + 1, ()).
node->right = constructMaximumBinaryTree(newVec);
}
return node.
Once these steps are done, you're basically done!
//Maximum binary tree
class Solution {
public.
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
TreeNode* node = new TreeNode(0);
if (() == 1) {
node->val = nums[0];
return node;
}
// found the largest element in this array and the subscript where the largest element is located
int maxValue = 0; int index = 0; return node; }
int index = 0; for (int i = 0; i
for (int i = 0; i < (); i++) {
if (nums[i] > maxValue) {
index = i; maxValue = nums[i] > maxValue) {
maxValue = nums[i];
}
}
// Assign a value to the root node
node->val = maxValue;
// Construct the left subtree (make sure the number of elements in the left array is ≥ 1)
if (index >= 1) {
vector<int> newVec((), () + index);
node->left = constructMaximumBinaryTree(newVec);
}
// Ensure that the number of elements in the right subtree is ≥ 1
if ((() - 1) - index > 0) {
vector<int> newVec(() + index + 1, ()).
node->right = constructMaximumBinaryTree(newVec);
}
return node.
}
};
advanced
Instead of applying extra array space, we can operate directly on the subscripts of the incoming array
class Solution {
public:
TreeNode* traversal(vector<int> &nums,int left,int right){
//When the left interval≥right interval (in calculus)，Then return to the
if(left>=right) return nullptr;
//Record the subscript of the maximum value
int maxValueIndex=left;
for(int i=left+1;i<right;i++){
if(nums[i]>nums[maxValueIndex]) maxValueIndex=i;
}
//Constructing the root node
TreeNode* node=new TreeNode(nums[maxValueIndex]);
//Constructing left and right subtrees
node->left=traversal(nums,left,maxValueIndex);
node->right=traversal(nums,maxValueIndex+1,right);
//Return to root node
return node;
}
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
return traversal(nums,0,());
}
};
summarize
Note that similar to the topic of constructing binary trees with arrays, each separation try not to define a new array, but through the subscript index directly on the original array operation, which can save time and space overhead.
When is a recursive function preceded by an if and when is it not?
In fact, it is the implementation of different code styles, in general: if the null node (null pointer) into the recursion, do not add if, if you do not let the null node into the recursion, add if restrictions, the termination conditions will also be adjusted accordingly.