难度中等442
给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。
示例 1:
输入: root = [2,1,3]
输出: 1示例 2:
输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7提示:
- 二叉树的节点个数的范围是
[1,104] -231 <= Node.val <= 231 - 1
1、迭代法
这道题使用层序遍历会比较简单，我们只要记录每一层第一个结点的值，这样子到了最后一层的话自然而然最后记录的就是最后一层第一个结点的值！
class Solution {
public:
int findBottomLeftValue(TreeNode* root) {
queue<TreeNode*> qe;
qe.push(root);
int result = 0;
while(!qe.empty())
{
int n = qe.size();
for(int i = 0; i < n; ++i)
{
TreeNode* cur = qe.front();
qe.pop();
// 每次记录每层第一个结点值
if(i == 0)
result = cur->val;
if(cur->left)
qe.push(cur->left);
if(cur->right)
qe.push(cur->right);
}
}
return result;
}
};2、递归法
其实我们递归的时候用前中后序都是没问题的，因为我们处理前中后三个结点的时候，并不关心中间结点的处理逻辑，我们只需要保证每次先往左边走，然后再往右边走的时候继续向左递进，所以三种遍历序列都是左子树优先于右子树，所以都是可以的！
其次，我们要找最深的那一层，那么我们可以用一个 MaxDepth 来代表最深那层的层数，而用 curDepth 来代表当前的层数！
若 curDepth > MaxDepth，说明需要更新一下 MaxDepth，并且我们用 result 代表每次更新最深高度时候的节点值，因为我们固定是先往左走，所以每次达到最深高度的时候，更新的结点一定是最左侧那个结点，这个不用担心！
💥💥还要需要注意的就是我们的 MaxDepth 和 result 是只有一份的，所以我们可以用传引用来实现维护一份的目的；而 curDepth 是每个栈帧中各自的一份，所以不能传引用！
class Solution {
public:
void find(TreeNode* root, int curDepth, int& MaxDepth, int& result)
{
if(root == nullptr)
return;
// 如果当前是叶子节点的话
if(root->left == nullptr && root->right == nullptr)
{
// 并且当前的深度高于最大深度，则我们更新最大深度和result，并且返回，相当于剪枝
if(curDepth > MaxDepth)
{
MaxDepth = curDepth;
result = root->val;
return;
}
}
// 继续递归到其左右子树进行查找
find(root->left, curDepth + 1, MaxDepth, result);
find(root->right, curDepth + 1, MaxDepth, result);
}
int findBottomLeftValue(TreeNode* root) {
int MaxDepth = INT_MIN; // 最深高度
int result = 0; // 最深高度对应的最左节点值
find(root, 1, MaxDepth, result);
return result;
}
};