513. 找树左下角的值
给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。
示例 1:
输入: root = [2,1,3]
输出: 1
示例 2:
输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7
解题思路：
- 层次遍历
本题用层次遍历非常容易理解，用队列去层次遍历二叉树，每次取出每层的第一个数，直到遍历完二叉树，取到的是最后一层中的第一个值，就是二叉树左下角的值。
代码：
class Solution { //513. 找树左下角的值 层次遍历
public:
int findBottomLeftValue(TreeNode* root) {
queue que;
int result;
if (root != nullptr) que.push(root);
while (!que.empty()) {
int length = que.size();
result = que.front()->val;
for (int i = 0; i < length; ++i) {
TreeNode* node = que.front();
que.pop();
if (node->left) que.push(node->left);
if (node->right) que.push(node->right);
}
}
return result;
}
};
- 递归遍历
递归遍历需要遇到叶子节点就记录下该层的深度，直到找到最大深度，第一次找到的最大深度的叶节点就是树的左下角。
（1）确定递归函数的参数和返回值：需要传入根节点，以及对应的层数。
（2）确定终止条件：遇到叶节点，如果该叶节点的深度大于最大深度，就对最大深度和左下角的值做更新。
（3）确定单层递归逻辑：如果当前节点的左子节点存在，继续往左子树找左下角的值；如果当前节点的右子节点存在，继续往右子树找左下角的值。
代码：
class Solution { //513. 找树左下角的值 递归遍历
public:
int maxLen = INT_MIN;
int maxleftValue;
void traversal(TreeNode* cur, int leftLen) {
if (cur->left == nullptr && cur->right == nullptr) {//叶节点
if (leftLen > maxLen) {
maxLen = leftLen;
maxleftValue = cur->val;
}
}
if (cur->left) {
traversal(cur->left, leftLen + 1);
}
if (cur->right) {
traversal(cur->right, leftLen + 1);
}
}
int findBottomLeftValue(TreeNode* root) {
traversal(root, 0);
return maxleftValue;
}
};
参考资料：代码随想录
