Given a binary tree, find the leftmost value in the last row of the tree.
Example 1:
Input:
2
/ \
1 3
Output:
1
Example 2:
Input:
1
/ \
2 3
/ / \
4 5 6
/
7
Output:
7
Note: You may assume the tree (i.e., the given root node) is not NULL.
这道题让我们求二叉树的最左下树结点的值，也就是最后一行左数第一个值，那么我首先想的是用先序遍历来做，我们维护一个最大深度和该深度的结点值，由于先序遍历遍历的顺序是根-左-右，所以每一行最左边的结点肯定最先遍历到，那么由于是新一行，那么当前深度肯定比之前的最大深度大，所以我们可以更新最大深度为当前深度，结点值res为当前结点值，这样在遍历到该行其他结点时就不会更新结果res了，参见代码如下：
解法一：
class Solution {
public:
int findBottomLeftValue(TreeNode* root) {int max_depth = 1, res = root->val;
helper(root, 1, max_depth, res);
return res;
}
void helper(TreeNode* node, int depth, int& max_depth, int& res) {
if (!node) return;
if (depth > max_depth) {
max_depth = depth;
res = node->val;
}
helper(node->left, depth + 1, max_depth, res);
helper(node->right, depth + 1, max_depth, res);
}
};
其实这道题用层序遍历更直接一些，因为层序遍历时遍历完当前行所有结点之后才去下一行，那么我们再遍历每行第一个结点时更新结果res即可，根本不用维护最大深度了，参见代码如下：
解法二：
class Solution {
public:
int findBottomLeftValue(TreeNode* root) {
int res = 0;
queue<TreeNode*> q{{root}};
while (!q.empty()) {
int n = q.size();
for (int i = 0; i < n; ++i) {
TreeNode *t = q.front(); q.pop();
if (i == 0) res = t->val;
if (t->left) q.push(t->left);
if (t->right) q.push(t->right);
}
}
return res;
}
};
我们还可以使用个小trick，使得其更加的简洁，由于一般的层序是从左往右的，那么如果我们反过来，每次从右往左遍历，这样就不用检测每一层的起始位置了，最后一个处理的结点一定是最后一层的最左结点，我们直接返回其结点值即可，参见代码如下：
解法三：
class Solution {
public:
int findBottomLeftValue(TreeNode* root) {
queue<TreeNode*> q{{root}};
while (!q.empty()) {
root = q.front(); q.pop();
if (root->right) q.push(root->right);
if (root->left) q.push(root->left);
}
return root->val;
}
};
参考资料：
https://leetcode.com/problems/find-bottom-left-tree-value/
LeetCode All in One 题目讲解汇总(持续更新中…)
转载请注明来源于 Grandyang 的博客 (grandyang.com)，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 grandyang@qq.com
