513. find the value in the lower left corner of the tree
Given the root of a binary tree, find the value of the leftmost node at the bottom of the tree.
Assume that there is at least one node in the binary tree.
Example 1.
Input: root = [2,1,3]
Output: 1
Example 2.
Input: [1,2,3,4,null,5,6,null,null,7]
Output: 7
Tip.
The number of nodes in a binary tree is in the range [1,104]
-231 <= <= 231 - 1
correct solution (a math. equation)
Let's analyze the topic: find the leftmost value in the last row of the tree.
First if it's the last line, then the leftmost value.
If you use the recursive method, how to determine that it is the last row, in fact, it is the leaf node with the largest depth must be the last row.
So look for the leaf node with the largest depth.
So how do you find the leftmost? You can use a preorder traversal that guarantees a preferential left search;
The leaf node with the greatest depth is then recorded, which at this point is the leftmost value in the last row of the tree.
- Determining the parameters and return values of a recursive function
The parameters must be the root node of the tree to be traversed, and an int variable to record the maximum depth. There would be no need for a return value here, so the return type of the recursive function would be void.
This question also requires two global variables in the class, maxLen to record the maximum depth and result to record the value of the leftmost node of the maximum depth. - Determination of termination conditions
When a leaf node is encountered, it's time to count the maximum depth, so you need to encounter the leaf node to update the maximum depth. - Determining the logic of single-level recursion
The recursion still uses backtracking when finding the maximum depth.
Upcode (●'◡'●)
class Solution {
public:
int maxDepth = INT_MIN;
int result;
void traversal(TreeNode* root, int depth) {
if (root->left == NULL && root->right == NULL) {
if (depth > maxDepth) {
maxDepth = depth;
result = root->val;
}
return;
}
if (root->left) {
traversal(root->left, depth + 1); // Hidden flashbacks.
}
if (root->right) {
traversal(root->right, depth + 1); // Hidden flashbacks.
}
return;
}
int findBottomLeftValue(TreeNode* root) {
traversal(root, 0);
return result;
}
};
112. Sum of paths
You are given the root node of a binary tree, root, and an integer targetSum that represents the target sum. Determine if there is a path from the root node to the leaf nodes in the tree whose values add up to the target sum targetSum. If so, returns true; otherwise, returns false.
Leaf node A node that has no children.
Example 1:
Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true
Explanation: root to leaf node path equal to target sum is shown above.
Example 2:
Input: root = [1,2,3], targetSum = 5
Output: false
Explanation : There are two paths from root node to leaf nodes in the tree:
(1 --> 2): and the sum is 3
(1 --> 3): sum is 4
There is no root-to-leaf path with sum = 5.
Example 3:
Input: root = [], targetSum = 0
Output: false
Explanation: Since the tree is empty, there is no path from root to leaf node.
Tip:
The number of nodes in the tree is in the range [0, 5000].
-1000 <= <= 1000
-1000 <= targetSum <= 1000
correct solution (a math. equation)
It is possible to traverse the binary tree using depth-first traversal (both pre-middle and post-middle order are fine for this question, it doesn't matter because there is no processing logic for the middle node either).
- Determining the parameters and return type of a recursive function
Parameters: need the root node of the binary tree, also need a counter, this counter is used to calculate whether the sum of one edge of the binary tree is exactly the target sum, the counter is of type int.
Return value: the traversal of the route, and do not traverse the entire tree, so the recursive function needs a return value, which can be expressed as a bool type. - Determination of termination conditions
How does the counter count the sum of this one path in the first place?
Do not go to accumulate and then determine whether it is equal to the target sum, then the code is more cumbersome, you can use the decrement, so that the counter count initially for the target sum, and then each time to subtract the traversed path node on the value.
If finally count == 0 while getting to the leaf node, it means that the target sum is found.
If the leaf node is traversed and count is not 0, it is not found. - Determining the logic of single-level recursion
Since the termination condition is to judge the leaf nodes, the recursion is done without letting empty nodes into the recursion.
Recursive functions have a return value. If the recursive function returns true, it means that a suitable path has been found and should be returned immediately.
Upcode (●'◡'●)
class Solution {
public:
bool hasPathSum(TreeNode* root, int sum) {
if (!root) return false;
if (!root->left && !root->right && sum == root->val) {
return true;
}
return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
}
};
As you can see, the code is lean, but hides many processes, including backtracking;
It should look like this if it's all unfolded:
class Solution {
private:
bool traversal(TreeNode* cur, int count) {
if (!cur->left && !cur->right && count == 0) return true; // Encountering leaf nodes，and the count is0
if (!cur->left && !cur->right) return false; // Encountering leaf nodes直接返回
if (cur->left) { // unorthodox
count -= cur->left->val; // recursive (calculation)，processing node;
if (traversal(cur->left, count)) return true;
count += cur->left->val; // look back upon，Withdrawal of results
}
if (cur->right) { // right (-hand)
count -= cur->right->val; // recursive (calculation)，processing node;
if (traversal(cur->right, count)) return true;
count += cur->right->val; // look back upon，Withdrawal of results
}
return false;
}
public:
bool hasPathSum(TreeNode* root, int sum) {
if (root == NULL) return false;
return traversal(root, sum - root->val);
}
};
106. Constructing Binary Trees by Traversing Sequences in Middle and Back Order
Given two arrays of integers inorder and postorder, where inorder is a middle-order traversal of a binary tree and postorder is a back-order traversal of the same tree, construct and return the binary tree.
Example 1.
Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
Output: [3,9,20,null,null,15,7]
Example 2.
Input: inorder = [-1], postorder = [-1]
Output: [-1]
Tip.
1 <= <= 3000
==
-3000 <= inorder[i], postorder[i] <= 3000
Both inorder and postorder consist of different values.
Every value in the postorder is in the inorder.
inorder is guaranteed to be a mid-order traversal of the tree.
The postorder is guaranteed to be a backward traversal of the tree.
correct solution (a math. equation)
First recall how to construct a unique binary tree based on two sequences:
The last element of the back-ordered array is used as the cut point, and the middle-ordered array is cut first;
Based on the middle-order array, in turn cut the back-order array.
Cutting down layer by layer, each time the last element of the back-ordered array is the node element.
When it comes to cutting layer by layer, recursion should come to mind.
Come and see how many steps there are:
-
Step 1: If the array size is zero, it means it's an empty node.
-
Step 2: If it is not empty, then take the last element of the back-ordered array as the node element.
-
Step 3: Find the position of the last element of the back-ordered array in the middle-ordered array as the cut point
-
Step 4: Cut the medium-order array into medium-order left and medium-order right arrays (pay attention to the order, must be the first cut medium-order array)
-
Step 5: Cut the back-ordered array into a back-ordered left array and a back-ordered right array
-
Step 6: Recursively process left and right intervals
Care should be taken at this point to determine the criteria for cutting, whether it is left-closed-right, and left-open-right, or left-closed-right;
This is the invariant to keep in the recursion.
In the process of cutting will produce four intervals, grasp the invariant is not good, a left closed right open, a left closed right closed, inevitably messy!
Why cut the medium-order array first?
The cut point is at the last element of the back-ordered array, which is used to cut the middle-ordered array, so it is necessary to cut the middle-ordered array first.
Middle-order arrays are relatively easy to cut, find the location of the cut point (the last element of the back-order array) in the middle-order array, and then cut the
The next step is to cut the back-ordered array.
First of all, the last element of the back-ordered array is specified as not wanted, which is the cut point and the element of the current middle node of the binary tree, which has been used.
How do you find the cut point of a back-ordered array?
Post-order arrays don't have explicit cut elements for left and right cuts, unlike mid-order arrays which have explicit cut points, and the cut points are just separated left and right.
One heavy point at this point is that the mid-order array size must be the same as the post-order array size (which is a given)
The middle-order arrays we've all cut up into left-middle and right-middle arrays;
Then the back-ordered array can be cut according to the size of the left-middle-ordered array, into a left-back-ordered array and a right-back-ordered array.
At this point, the mid-order array is cut into a left mid-order array and a right mid-order array, and the back-order array is cut into a left back-order array and a right back-order array.
Next you can recursively.
Upcode (●'◡'●)
class Solution {
private:
TreeNode* traversal (vector<int>& inorder, vector<int>& postorder) {
if (() == 0) return NULL;
// Iterate over the last element of the array in backward order，is the current intermediate node
int rootValue = postorder[() - 1];
TreeNode* root = new TreeNode(rootValue);
// leaf node
if (() == 1) return root;
// Finding cut points for mid-order traversals
int delimiterIndex;
for (delimiterIndex = 0; delimiterIndex < (); delimiterIndex++) {
if (inorder[delimiterIndex] == rootValue) break;
}
// Cutting mid-order arrays
// Left-Close-Right-Open Interval：[0, delimiterIndex)
vector<int> leftInorder((), () + delimiterIndex);
// [delimiterIndex + 1, end)
vector<int> rightInorder(() + delimiterIndex + 1, () );
// postorder Discard end elements
(() - 1);
// Cutting back-ordered arrays
// Still closed on the left and open on the right.，Note that the left-middle array size is used here as the cut point
// [0, )
vector<int> leftPostorder((), () + ());
// [(), end)
vector<int> rightPostorder(() + (), ());
root->left = traversal(leftInorder, leftPostorder);
root->right = traversal(rightInorder, rightPostorder);
return root;
}
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
if (() == 0 || () == 0) return NULL;
return traversal(inorder, postorder);
}
};
It's not easy to write a blog, so please give me some support 8~!