【513. 找树左下角的值】

来源：力扣（LeetCode）

描述：

给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。

假设二叉树中至少有一个节点。
示例 1:

输入: root = [2,1,3]
输出: 1
1
2

示例 2:

输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7
1
2

提示:

• 二叉树的节点个数的范围是 [1,10⁴]
• -2³¹ <= Node.val <= 2³¹ - 1

方法一：深度优先搜索
使用 height 记录遍历到的节点的高度， curVal 记录高度在 curHeight 的最左节点的值。在深度优先搜索时，我们先搜索当前节点的左子节点，再搜索当前节点的右子节点，然后判断当前节点的高度 height 是否大于 curHeight，如果是，那么将 curVal 设置为当前结点的值， curHeight 设置为 height。

因为我们先遍历左子树，然后再遍历右子树，所以对同一高度的所有节点，最左节点肯定是最先被遍历到的。

代码：

class Solution {
public:
    void dfs(TreeNode *root, int height, int &curVal, int &curHeight) {
        if (root == nullptr) {
            return;
        }
        height++;
        dfs(root->left, height, curVal, curHeight);
        dfs(root->right, height, curVal, curHeight);
        if (height > curHeight) {
            curHeight = height;
            curVal = root->val;
        }
    }

    int findBottomLeftValue(TreeNode* root) {
        int curVal, curHeight = 0;
        dfs(root, 0, curVal, curHeight);
        return curVal;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

执行用时：4 ms, 在所有 C++ 提交中击败了97.07%的用户
内存消耗：21 MB, 在所有 C++ 提交中击败了97.09%的用户
复杂度分析
时间复杂度： O(n)，其中 n 是二叉树的节点数目。需要遍历 n 个节点。
空间复杂度： O(n)。递归栈需要占用 O(n) 的空间。

方法二：广度优先搜索

使用广度优先搜索遍历每一层的节点。在遍历一个节点时，需要先把它的非空右子节点放入队列，然后再把它的非空左子节点放入队列，这样才能保证从右到左遍历每一层的节点。广度优先搜索所遍历的最后一个节点的值就是最底层最左边节点的值。

代码：

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        int ret;
        queue<TreeNode *> q;
        q.push(root);
        while (!q.empty()) {
            auto p = q.front();
            q.pop();
            if (p->right) {
                q.push(p->right);
            }
            if (p->left) {
                q.push(p->left);
            }
            ret = p->val;
        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

执行用时：8 ms, 在所有 C++ 提交中击败了81.05%的用户
内存消耗：21.1 MB, 在所有 C++ 提交中击败了62.89%的用户

author：LeetCode-Solution添加链接描述