654. Maximum binary tree
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.
Example 2:
- The maximum value in [3,2,1] is 3, the left part is [] and the right part is [2,1].
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.
correct solution (a math. equation)
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.
- Determining the parameters and return values of a recursive function
The parameter passed in is an array holding the elements, returning the head node of the binary tree constructed from that array, and the return type is a pointer to a node. - Determination of termination conditions
The question says that the input array size must be greater than or equal to 1, so we don't have to consider the case of less than 1. Then when traversing recursively, if the incoming array size is 1, it means that the traversal has reached the leaf node.
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. - Determining the logic of single-level recursion
There are three steps at work here
- The first step is to find the largest value in the array and the corresponding subscript. The largest value is used to construct the root node and the subscript is used to split the array in the next step.
- Left interval of the subscript where the maximum value is located Construct left subtree
Here it is necessary to determine maxValueIndex > 0, because it is necessary to ensure that there is at least one value in the left interval. - Right interval of the subscript where the maximum value is Construct right subtree
Determine maxValueIndex < (() - 1) to ensure that the right interval has at least one value.
Upcode (●'◡'●)
class Solution {
public:
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
TreeNode* node = new TreeNode(0);
if (() == 1) {
node->val = nums[0];
return node;
}
// Find the largest value in the array and the corresponding subscripts
int maxValue = 0;
int maxValueIndex = 0;
for (int i = 0; i < (); i++) {
if (nums[i] > maxValue) {
maxValue = nums[i];
maxValueIndex = i;
}
}
node->val = maxValue;
// The left interval of the subscript where the maximum value is located Constructing the left subtree
if (maxValueIndex > 0) {
vector<int> newVec((), () + maxValueIndex);
node->left = constructMaximumBinaryTree(newVec);
}
// The right interval of the subscript where the maximum value is located Constructing the right subtree
if (maxValueIndex < (() - 1)) {
vector<int> newVec(() + maxValueIndex + 1, ());
node->right = constructMaximumBinaryTree(newVec);
}
return node;
}
};
617. Merging binary trees
You are given two binary trees: root1 and root2.
Imagine that when you overlay one on top of the other, some nodes on the two trees will overlap (and others won't). You need to merge these two trees into a new binary tree. The rule for merging is: if the two nodes overlap, then the values of the two nodes will be added together as the new value of the merged node; otherwise, the node that is not null will be directly used as the node of the new binary tree.
Returns the merged binary tree.
Note: The merge process must start at the root node of both trees.
Example 1:
Input: root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
Output: [3,4,5,5,4,null,7]
Example 2:
Input: root1 = [1], root2 = [1,2]
Output: [2,2]
Tip:
The number of nodes in both trees is in the range [0, 2000].
-104 <= <= 104
correct solution (a math. equation)
When using recursion for a binary tree, you have to think about which traversal to use before, during and after?
Either traversal is fine to use for this question!
Let's take the following example of a previous order traversal.
- Determines the parameters and return values of a recursive function:
First of all to merge into two binary trees, then the parameter is at least to pass the root node of the two binary trees, the return value is the root node of the binary tree after the merger. - Determine the conditions for termination:
Because two trees are passed in, then there are two tree traversal nodes t1 and t2, if t1 == NULL, the two trees should be merged with t2 (if t2 is also NULL, it doesn't matter, after the merger is NULL).
In turn if t2 == NULL, then the two numbers are merged to be t1 (it doesn't matter if t1 is also NULL, it's NULL after the merge).
3. Determine the logic of single-level recursion:
The logic of single-level recursion is a bit easier to write, and here we reuse the tree t1, which is the root node of the tree after the merge (that is, it modifies the structure of the original tree).
Then in single level recursion, the elements of the two trees have to be added together.
The next left subtree of t1 is: the left subtree after merging the left subtree of t1 with the left subtree of t2.
right subtree of t1: is the right subtree after merging the right subtree of t1 with the right subtree of t2.
Eventually t1 is the root node after the merger.
Upcode (●'◡'●)
class Solution {
public.
TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
if (t1 == NULL) return t2; // if t1 is null, then t2 should be merged
if (t2 == NULL) return t1; // if t2 is null, the merge should be t1
// Modify the value and structure of t1
t1->val += t2->val; // in
t1->left = mergeTrees(t1->left, t2->left); // left
t1->right = mergeTrees(t1->right, t2->right); // right
return t1; }
}
}.
It's not easy to write a blog, so please give me some support!