Title Link:/problems/find-bottom-left-tree-value/description/
Title Narrative:
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,10^4].
-2^31 <= <= 2^31 - 1
Thoughts:
We have two ways to write this question, recursion and iteration, we focus on the recursive solution here, if we use the iterative method of hierarchical traversal, we have a very simple question, but I will also introduce the hierarchical traversal writing method later.
recursive method
What we must be clear about the recursive method is three things:
- Arguments to be passed to our recursive function and the return value of the recursive function
- Conditions for the end of recursion (a.k.a. recursion boundaries)
- The logic of single-level recursion
In fact, the recursion in this question also contains the logic of backtracking, in fact, all recursive algorithms can not be separated from the backtracking, just that we do not realize the process of backtracking, or the backtracking process is hidden.
I'll highlight the backtracking logic in the code below
Step 1. Determine our parameters and return values
The parameter for this question, since it is asking for the leftmost node of the last layer, we are bound to use a parameterdepthto represent the depth, and then we also need a parametermaxdepthto indicate whether the maximum depth has been reached.maxdepthVariables are not required
Passed into the function, we can define it as a global variable. If depth > maxdepth, it proves that the current maximum depth has not been reached, and it is not the leftmost node we want to deal with. Also, we need a parameterresultto receive the nodes we need to find this node's node
value, this variable we also define as a global variable.
Determining the abort condition for recursion
What node are we dealing with? Is it a leaf node, what is our logical judgment to deal with leaf nodes? Is it only necessary to the current node its left and right children are empty, we have reached the time we need to deal with, this time is the time to return.
So what are the things we have to do to process this node? --we're going to determine if the current depth is the maximum depth, and if it's not, we're going to have to update that maximum depth, and at the same time we're going to have to update the value of the result variable, and then we're going to return, and that takes care of the recursive boundary conditions, the
Right?
The code for this logic is as follows:
//return when processing reaches a leaf node
if(cur->left==NULL&&cur->right==NULL){
if(depth>maxdepth){
maxdepth=depth.
result=cur->val;
}
return;
}
The logic of single-level recursion
Now that we've found the deepest leaf node, how do we make sure it's the leftmost node? That's easy! All we need to do is to prioritize the left child when dealing with the recursion, so we can make sure we are dealing with the left child first! Right?
The code for this logic is as follows:
if(cur->left!=NULL){
//Let depth++ first and let him handle the next level of nodes
depth++;
traversal(cur->left,depth).
// then let depth--, which is the process of backtracking, backing up to the node in the previous level and then processing the right subtree
depth--;
}
if(cur->right!=NULL){
// Same thing here
depth++;
traversal(cur->right,depth).
// Same thing here with the backtracking
depth--;
}
In fact, after dealing with these boundary conditions, our code comes out
Overall Code:
class Solution {
public.
int result=0; int maxdepth=INT_MIN; class Solution { public.
int maxdepth=INT_MIN; void traversal(TreeNode*cur,int depth){
void traversal(TreeNode*cur,int depth){
// Return when the process reaches a leaf node
if(cur->left==NULL&&cur->right==NULL){
if(depth>maxdepth){
maxdepth=depth.
result=cur->val;
}
return;
}
if(cur->left!=NULL){
// let depth++ first, so he can handle the next level of nodes
depth++;
traversal(cur->left,depth).
// then let depth--, which is the process of backtracking, backing up to the node in the previous level and then processing the right subtree
depth--;
}
if(cur->right!=NULL){
// Same thing here
depth++;
traversal(cur->right,depth).
// Same thing here with the backtracking
depth--;
}
}
int findBottomLeftValue(TreeNode* root) {
traversal(root,0);
return result; }
}
}; }
Hierarchical traversal (iterative method)
In fact, this question using layer order traversal is the most convenient, the simplest approach. We only need to deal with the first element of each layer, and then processed to the last layer, it is naturally the last layer of the first element on the left, this question only need to layer order traversal of the template above the change a little bit!
It will be realized!
If you don't know how to layer traversal, I recommend checking out my article on layer traversal, which explains the process of implementing layer traversal in detail!
Layer-order traversal:/Tomorrowland/p/18318744
class Solution {
public:
int findBottomLeftValue(TreeNode* root) {
queue<TreeNode*> que;
if (root != NULL) (root);
int result = 0;
while (!()) {
int size = ();
for (int i = 0; i < size; i++) {
TreeNode* node = ();
();
if (i == 0) result = node->val; // Record the first element of the last line
if (node->left) (node->left);
if (node->right) (node->right);
}
}
return result;
}
};