找树左下角的值 图解题解

这道题到底在问什么

树

[1,2,3,4,null,5,6,null,null,7]

第1层

1

第2层

2 3

第3层

4 5 6

第4层(最底)

7 ← 答案

最优解：一步一步想明白

1. 3如果一条道走到黑，先撞到底的不一定在最左边。我们需要一种「先把每一层从左到右走完，再下一层」的走法——这正是层序遍历（BFS）。
2. 4关键技巧：每一层开始时，队首就是这一层最左边的节点。我们每进入新一层都更新一次「本层第一个」，自然地，最后那一层留下的就是最底层最左节点。下面一帧一帧看队列怎么动。
3. 5answer 暂存 = 根 1这是示例树。第 4 层只有一个 7，凭肉眼一眼能看出答案是 7。但代码看不见全局，它要靠队列一层层扫。开局：队列里放进根 1，answer 先用根 1 兜底。
4. 6size=1，i=0 → answer = 1进入第 1 层。先记下本层节点个数 size=1。i=0 取出的队首 1 就是本层第一个，更新 answer = 1。橙色就是正在处理的节点。
5. 7弹出 1，压入 2、3把 1 出队（变绿表示处理完），按先左后右把它的孩子 2、3 依次压入队尾。第 1 层扫完，队列里正好排着下一层从左到右的节点：[2, 3]。
6. 8size=2，i=0 → answer = 2进入第 2 层。先量好本层 size=2（这是进入循环前队列里的节点数，刚好是这一层的全部）。i=0 的队首 2 就是本层最左，更新 answer = 2。
7. 9size 锁定 = 2，开始 for 循环动手出队前，size=2 已经锁死——这是「框住一层」的关键。接下来 for 只跑 i=0、i=1 两次，正好处理 2、3 这两个；中途压进去的孩子属于下一层，不会被这轮吞掉。
8. 10弹出 2，压入左孩子 4把队首 2 出队（变绿）。2 只有左孩子 4，把 4 压入队尾；2 没有右孩子就跳过。入队前要判空——空孩子不进队列，否则会乱。现在队列 = [3, 4]。
9. 11弹出 3，压入 5、6继续把本层第二个 3 出队（橙色处理中），先左 5 后右 6 依次入队。第 2 层的两个节点都处理完了。注意 answer 这一层始终是 2，没被覆盖——因为只有 i=0 时才更新。
10. 12本层 size=2 个都出队了本层量好的 size=2 个节点都出队了，第 2 层结束。此刻队列里 [4, 5, 6] 正好是第 3 层从左到右的全部节点。这就是「按 size 一批一批处理」能精准分层的原理。
11. 13size=3，i=0 → answer = 4进入第 3 层，量好 size=3。i=0 的队首 4 是本层最左，更新 answer = 4。橙色的 4 正在处理。
12. 14弹出 4，无孩子入队把队首 4 出队（变绿）。4 是叶子，左右孩子都为空，什么都不入队。队列变成 [5, 6]。answer 这层锁定在 4 不变。
13. 15i = 1，队首移到 5本层 for 的 i 前进到 1，队首轮到 5（橙色）。i 已经不是 0 了，所以这一层 answer 不再更新，稳稳停在最左的 4。接下来处理 5 的孩子。
14. 16弹出 5，压入左孩子 7本层第二个 5 出队（橙色处理中）。5 有左孩子 7，把 7 压入队尾；没有右孩子就跳过。第 4 层的唯一节点 7 现在排进了队列。
15. 17i = 2，队首移到 6i 再前进到 2，队首轮到本层最后一个 6（橙色）。注意此刻队列尾部已经排着下一层的 7。answer 依旧是 4——本层只有 i=0 那一刻更新过。
16. 18弹出 6，无孩子入队本层最后一个 6 出队（橙色）。6 是叶子，没有孩子。第 3 层的 size=3 个节点全处理完，第 3 层结束。这一层 answer 始终是 4，因为后面的 5、6 都不是 i=0。
17. 19队列 = [7] 即最底层第 3 层全部出队，队列里只剩一个 7——它正是最底层（第 4 层）从左到右的全部。队列非空，说明还有一层要处理，循环继续。
18. 20size=1，i=0 → answer = 7进入第 4 层，量好 size=1。i=0 的队首 7 是本层最左，更新 answer = 7。这是目前最深的一层，answer 被刷到了 7。
19. 21弹出 7，无孩子，队列空把 7 出队（变绿）。7 是叶子，没有孩子入队，队列空了。下一轮 while 条件不成立，循环结束。最后一次被记下的 answer 就是 7。
20. 22队列空，返回 answer队列空，BFS 结束。answer 经历 1 → 2 → 4 → 7 一路被更深一层的最左节点刷新，最终停在 7。它正是最底层最左节点，返回它。
21. 25一句话记住它：先量 size 把一层「框」出来，i==0 那个就是本层最左；让更深的层不断覆盖答案，最后定格在最底层最左。
22. 27若每出队就更新 → 第2层 ans 变成 3看这个错法：第 2 层每出队一个就更新 ans，2 刚记上，3 又把它覆盖，本层「最左」就变成了「最右」。正确做法只在 i==0 那一次更新，守住本层最左。
23. 28不固定 size → 第2层混入第3层另一个坑：进 for 前不先把 size 记死，循环中又往队尾加了 4、5、6，结果把下一层也算进本层。一定要先 size = len(q) 把这一层框住，只处理这么多个。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from collections import deque
class Solution:
    def findBottomLeftValue(self, root):
        q = deque([root])              # 根入队
        ans = root.val
        while q:                       # 一层一层
            size = len(q)              # 本层节点数
            for i in range(size):
                node = q.popleft()     # 出队
                if i == 0:             # 本层第一个
                    ans = node.val     # 记为答案
                if node.left:
                    q.append(node.left)   # 先左
                if node.right:
                    q.append(node.right)  # 后右
        return ans                 # 最底层最左

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        queue<TreeNode*> q;
        q.push(root);                       // 根入队
        int ans = root->val;
        while (!q.empty()) {                // 一层一层
            int size = q.size();            // 本层节点数
            for (int i = 0; i < size; ++i) {
                TreeNode* node = q.front(); q.pop(); // 出队
                if (i == 0) ans = node->val;    // 本层第一个
                if (node->left)  q.push(node->left);  // 先左
                if (node->right) q.push(node->right); // 后右
            }
        }
        return ans;                         // 最底层最左
    }
};

class Solution {
    public int findBottomLeftValue(TreeNode root) {
        Deque<TreeNode> q = new ArrayDeque<>();
        q.offer(root);                          // 根入队
        int ans = root.val;
        while (!q.isEmpty()) {                  // 一层一层
            int size = q.size();                // 本层节点数
            for (int i = 0; i < size; i++) {
                TreeNode node = q.poll();       // 出队
                if (i == 0) ans = node.val;     // 本层第一个
                if (node.left != null)  q.offer(node.left);  // 先左
                if (node.right != null) q.offer(node.right); // 后右
            }
        }
        return ans;                             // 最底层最左
    }
}

复杂度

面试官可能追问