找树左下角的值

如果一条道走到黑，先撞到底的不一定在最左边。我们需要一种「先把每一层从左到右走完，再下一层」的走法——这正是层序遍历（BFS）。

关键技巧：每一层开始时，队首就是这一层最左边的节点。我们每进入新一层都更新一次「本层第一个」，自然地，最后那一层留下的就是最底层最左节点。下面一帧一帧看队列怎么动。

整棵树 · 准备 BFS：这是示例树。第 4 层只有一个 7，凭肉眼一眼能看出答案是 7。但代码看不见全局，它要靠队列一层层扫。开局：队列里放进根 1，answer 先用根 1 兜底。

第1层开始 · 队首 1 是本层第一个：进入第 1 层。先记下本层节点个数 size=1。i=0 取出的队首 1 就是本层第一个，更新 answer = 1。橙色就是正在处理的节点。

出队 1 · 孩子 2、3 入队：把 1 出队（变绿表示处理完），按先左后右把它的孩子 2、3 依次压入队尾。第 1 层扫完，队列里正好排着下一层从左到右的节点：[2, 3]。

第2层开始 · 队首 2 是本层第一个：进入第 2 层。先量好本层 size=2（这是进入循环前队列里的节点数，刚好是这一层的全部）。i=0 的队首 2 就是本层最左，更新 answer = 2。

本层准备出队 · 框住第2层：动手出队前，size=2 已经锁死——这是「框住一层」的关键。接下来 for 只跑 i=0、i=1 两次，正好处理 2、3 这两个；中途压进去的孩子属于下一层，不会被这轮吞掉。

出队 2 · 孩子 4 入队：把队首 2 出队（变绿）。2 只有左孩子 4，把 4 压入队尾；2 没有右孩子就跳过。入队前要判空——空孩子不进队列，否则会乱。现在队列 = [3, 4]。

出队 3 · 孩子 5、6 入队：继续把本层第二个 3 出队（橙色处理中），先左 5 后右 6 依次入队。第 2 层的两个节点都处理完了。注意 answer 这一层始终是 2，没被覆盖——因为只有 i=0 时才更新。

第2层结束 · 队列正是第3层：本层量好的 size=2 个节点都出队了，第 2 层结束。此刻队列里 [4, 5, 6] 正好是第 3 层从左到右的全部节点。这就是「按 size 一批一批处理」能精准分层的原理。

第3层开始 · 队首 4 是本层第一个：进入第 3 层，量好 size=3。i=0 的队首 4 是本层最左，更新 answer = 4。橙色的 4 正在处理。

出队 4 · 叶子无孩子：把队首 4 出队（变绿）。4 是叶子，左右孩子都为空，什么都不入队。队列变成 [5, 6]。answer 这层锁定在 4 不变。

本层 i 前进 · 看下一个 5：本层 for 的 i 前进到 1，队首轮到 5（橙色）。i 已经不是 0 了，所以这一层 answer 不再更新，稳稳停在最左的 4。接下来处理 5 的孩子。

出队 5 · 孩子 7 入队：本层第二个 5 出队（橙色处理中）。5 有左孩子 7，把 7 压入队尾；没有右孩子就跳过。第 4 层的唯一节点 7 现在排进了队列。

本层 i 前进 · 看最后一个 6：i 再前进到 2，队首轮到本层最后一个 6（橙色）。注意此刻队列尾部已经排着下一层的 7。answer 依旧是 4——本层只有 i=0 那一刻更新过。

出队 6 · 叶子无孩子：本层最后一个 6 出队（橙色）。6 是叶子，没有孩子。第 3 层的 size=3 个节点全处理完，第 3 层结束。这一层 answer 始终是 4，因为后面的 5、6 都不是 i=0。

第3层结束 · 队列只剩第4层的 7：第 3 层全部出队，队列里只剩一个 7——它正是最底层（第 4 层）从左到右的全部。队列非空，说明还有一层要处理，循环继续。

第4层开始 · 队首 7 是本层第一个：进入第 4 层，量好 size=1。i=0 的队首 7 是本层最左，更新 answer = 7。这是目前最深的一层，answer 被刷到了 7。

出队 7 · 叶子无孩子 → 队列空：把 7 出队（变绿）。7 是叶子，没有孩子入队，队列空了。下一轮 while 条件不成立，循环结束。最后一次被记下的 answer 就是 7。

循环结束 · 返回 answer = 7：队列空，BFS 结束。answer 经历 1 → 2 → 4 → 7 一路被更深一层的最左节点刷新，最终停在 7。它正是最底层最左节点，返回它。

一句话记住它：先量 size 把一层「框」出来，i==0 那个就是本层最左；让更深的层不断覆盖答案，最后定格在最底层最左。

易错实演 · 每个都更新会取到最右：看这个错法：第 2 层每出队一个就更新 ans，2 刚记上，3 又把它覆盖，本层「最左」就变成了「最右」。正确做法只在 i==0 那一次更新，守住本层最左。

易错实演 · 不量 size 分层就乱：另一个坑：进 for 前不先把 size 记死，循环中又往队尾加了 4、5、6，结果把下一层也算进本层。一定要先 size = len(q) 把这一层框住，只处理这么多个。

三个边界：单节点直接返回根；退化成一条链时每层仅一节点、自然逐层覆盖；最底层即便只有一个右孩子，它也是那层的 i==0，照样被取到。

面试常追问三点：BFS 怎么精准分层（先量 size）、能否 DFS（带深度、第一次到更深层时更新）、要最右怎么改（入队顺序或更新时机反过来）。