LeetCode LCR 045. 找树左下角的值
目录
题目描述
题意分析
题目目标：在一棵非空二叉树里找到"最底层最靠左"的那个节点的值，也就是深度最大的那些节点中位置最左的一个。
核心约束：判定标准是两级排序——先比深度（越深越优），深度相同再比水平位置（越左越优）。注意"最靠左"指的是该层从左往右数的第一个节点，而不是"沿着左孩子一路走到底"，这两者在最深层由右孩子产生时会给出完全不同的答案。
边界处理：题目保证树至少有一个节点，所以答案一定存在；只有根时答案就是根值；最深层可能只包含某个节点的右孩子，此时它同时也是该层最左的节点。
实现取舍：只要遍历方式能保证"更深的层后被处理"且"同层从左往右处理"，答案就是最后一次记录下来的那个层首值，不需要保存整棵树的结构。
解法：深度优先搜索
核心思路
朴素思路是先算出树的最大深度，再遍历一遍把处于该深度的节点收集起来取第一个。要走两遍树，还要额外维护一个列表，逻辑上也容易在"第一个"的定义上出错。
观察这道题的判定标准与逐层推进的遍历顺序天然匹配：如果按层从上到下、层内从左到右地访问节点，那么每一层被访问到的第一个节点就是这一层的最左节点；层的处理顺序又保证越深的层越晚被处理。两个条件叠加，最后一层的最左节点必然是整个过程中最后一次被记录的层首。
由此确定不变量：每轮外层循环开始时，容器q里恰好是当前层从左到右排列的全部节点；内层循环按快照长度消费这些节点，其中下标i == 0的那个就是本层最左节点，用它无条件覆盖answer。
"无条件覆盖"是这个写法的精髓——不需要比较深度，也不需要判断是不是最后一层，因为越深的层越晚覆盖，循环自然结束时answer里留下的就是最深层的最左值。
解题步骤
- 把根节点入队，
answer先置为任意值（这里是 -1）。为什么初值无所谓：树非空保证至少有一层会被处理，第一轮就会把answer覆盖成根值，初值永远不会被返回。- 外层循环以"容器非空"为条件推进层。为什么这个条件正确：不变量保证容器里装的就是下一个待处理层，容器为空说明所有层都处理完了。
- 每轮先用
int n = q.size()把本层节点数快照下来。为什么必须快照：内层循环会向同一个容器追加下一层节点，若把长度写进循环条件反复求值，下一层的节点会被当成本层，i == 0的语义随之失效。- 内层按下标
i从 0 递增地消费节点，遇到i == 0就执行answer = node.val。为什么下标 0 就是最左：本层节点是上一轮按"先左孩子后右孩子"的顺序入队的，队首即最左。- 消费每个节点时把非空的左孩子、右孩子依次入队。为什么左先右后不能颠倒：正是这个顺序保证了下一层在容器中的排列仍是从左到右，是
i == 0等于最左这条推论的唯一依据。- 全部循环结束后返回
answer。为什么它就是答案：它被最后一层的层首覆盖过，而最后一层就是最深层。- 以
具体用例：树[1, 2, 3, 4, null, 5, 6, null, null, 7]（根 1；第二层 2、3；第三层 4 是 2 的左孩子，5、6 是 3 的左右孩子；第四层 7 是 5 的左孩子）走一遍。第一轮容器[1]，i = 0使answer = 1，入队 2、3。第二轮容器[2, 3]，i = 0时节点是 2 使answer = 2，依次入队 4、5、6。第三轮容器[4, 5, 6]，i = 0时节点是 4 使answer = 4，其中 5 入队孩子 7。第四轮容器[7]，i = 0使answer = 7，无新孩子。容器变空，返回 7。注意 7 是通过"右孩子 5"这条路径下来的，若按"一路走左孩子"的错误理解会得到 4。
代码实现
// 核心实现：深度优先搜索，维护必要状态并避免重复处理。
class Solution {
public int findBottomLeftValue(TreeNode root) {
Queue<TreeNode> q = new ArrayDeque<>();
q.offer(root);
int answer = -1;
while (!q.isEmpty()) {
int n = q.size();
for (int i = 0; i < n; i++) {
TreeNode node = q.poll();
if (i == 0) {
answer = node.val;
}
if (node.left != null) {
q.offer(node.left);
}
if (node.right != null) {
q.offer(node.right);
}
}
}
return answer;
}
}
// 核心实现：深度优先搜索，维护必要状态并避免重复处理。
func findBottomLeftValue(root *TreeNode) int {
q := []*TreeNode{root}
answer := -1
for n := len(q); n > 0; n = len(q) {
for i := 0; i < n; i++ {
node := q[0]
q = q[1:]
if i == 0 {
answer = node.Val
}
if node.Left != nil {
q = append(q, node.Left)
}
if node.Right != nil {
q = append(q, node.Right)
}
}
}
return answer
}
复杂度分析
- 时间复杂度：$O(n)$。凭什么：每个节点恰好入队一次、出队一次，出队时只做一次下标判断与至多两次入队，没有任何重复访问。
- 空间复杂度：$O(w)$，
w为最大层宽，最坏为 $O(n)$。凭什么：容器在任意时刻只同时容纳相邻两层的部分节点，除此之外只有一个整型答案变量。
关键点总结
- 当答案的判定标准是"深度优先、同深度再看位置"时，逐层推进的遍历顺序本身就编码了这个排序，于是"取最后一次记录"这种覆盖式写法可以完全取代显式的深度比较。
- "最左"是层内位置概念，不是路径概念；把它误解成"一路向左"是这题最典型的思维陷阱，判断时始终要回到层序排列上。
- 内层循环的长度快照是分层写法的命门，任何在循环条件里重新求容器长度的写法都会让层边界失效。
- 入队顺序（先左后右）不是随手写的，它是"队首即最左"这条推论的前提，改动它就必须同步改动取值位置。
- 面试视角：面试官常追问递归写法。递归时传入当前深度，只在
depth > maxDepth时更新答案并抬高maxDepth，且必须先递归左子树——用严格大于保证同深度时先到的（更左的）节点胜出。能说清"迭代版靠顺序隐式排序、递归版靠严格大于显式排序"这组对偶关系，这题就答满了。
易错点总结
- 错误写法：把题意理解成一路沿左孩子走到底 → 树
[1, 2, 3, null, null, 4]（3 的左孩子是 4）时正确答案是 4，该写法返回 2。- 错误写法：内层循环条件写成
i < q.size()而不是快照n→ 树[1, 2, 3]时第二层节点被并入第一层，i == 0只在整棵树的第一个节点触发，答案永远是根值 1。- 错误写法：入队时先右后左 → 树
[1, 2, 3]时第二层排列成[3, 2]，返回 3 而不是正确的 2。- 错误写法：记录条件写成
i == n - 1→ 变成了求最底层最右值，树[1, 2, 3]返回 3 而不是 2。- 错误写法：递归版把更新条件写成
depth >= maxDepth→ 树[1, 2, 3]中第二层的 2 先被记录，随后 3 以相同深度覆盖，返回 3 而不是 2。- 错误写法：递归版先递归右子树再递归左子树，同时用严格大于 → 树
[1, 2, 3]时 3 先到达深度 2 并被记录，左边的 2 因为不满足严格大于被忽略，返回 3。- 错误写法：把空孩子也入队 → 空节点占据队首位置，
i == 0时访问node.val直接空指针异常。- 错误写法：在循环外提前
return answer，或把返回值写在内层循环结束处 → 只处理了第一层就返回，树[1, 2, 3]返回 1。- 错误写法：把
answer的更新改成"只在容器为空前的最后一轮记录"，靠额外标志判断是不是最后一层 → 需要提前知道下一层是否为空，标志更新一旦晚一拍，树高为 1 的情形直接返回初值 -1。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 102. 二叉树的层序遍历 | 中等 | 需要输出每层完整列表，考察分层结果的收集 |
| 199. 二叉树的右视图 | 中等 | 取每层末位而非仅最深层，答案是数组不是单值 |
| LCR 044. 在每个树行中找最大值 | 中等 | 层内聚合规则换成取最大值，需处理负数初值 |
| 103. 二叉树的锯齿形层序遍历 | 中等 | 层内方向按奇偶交替，考察顺序反转 |
| 1302. 层数最深叶子节点的和 | 中等 | 同样只关心最深层，但要对整层求和而非取首个 |
| 958. 二叉树的完全性检验 | 中等 | 层序遍历用于判定形状，必须把空位一并入队 |