LeetCode 513. 找树左下角的值
题目描述
题意分析
先找到树的最深一层，再返回这一层最靠左节点的值。最深节点也可能位于根的右子树，必须遍历整棵树才能确定最终层。
层序遍历恰好按深度从小到大访问节点。只要让每层按从左到右的顺序出队，就能取这一层第一个节点作为候选；更深一层出现时覆盖候选，最后留下的就是答案。
解法：层序遍历记录每层第一个节点
核心思路
[!blue]
每轮开始时，队列中尚未处理的节点恰好属于同一层，并按从左到右排列。最初只有根，顺序成立；处理一层时，先处理靠左的父节点，并对每个父节点先加入左孩子、再加入右孩子，因此下一层仍保持从左到右的顺序。缺失的孩子直接跳过，不影响已有节点的相对位置。
size表示本层尚未处理的节点数，必须在加入下一层孩子之前固定。内层循环恰好取出size个节点，因此i == 0时取出的就是本层最左节点，用它的值覆盖ans。这一层处理完后，剩余待处理节点恰好组成下一层。Java 出队会移除节点，直接用
queue.size()得到本层大小。Go 用head指向下一个待处理节点，切片还保留已经处理的前缀，所以本层大小是len(queue) - head。每一轮结束后，
ans都是目前最深层的最左值；队列处理完时不再存在更深节点，因此它就是整棵树的答案。题目保证根非空，用root.val初始化也覆盖了只有根节点的情况。
解题步骤
- 将根入队。
- 在每轮开始保存本层待处理数量。
- 处理本层第一个节点时更新答案。
- 依次加入左、右孩子，随后继续下一层。
代码实现
class Solution {
public int findBottomLeftValue(TreeNode root) {
Queue<TreeNode> queue = new ArrayDeque<>();
queue.offer(root);
int ans = root.val;
while (!queue.isEmpty()) {
// 在加入下一层之前固定本层节点数量
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (i == 0) {
// 当前层第一个访问到的节点就是这一层最左节点。
ans = node.val;
}
// 左孩子先入队，维持下一层从左到右
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
return ans;
}
}
func findBottomLeftValue(root *TreeNode) int {
queue := make([]*TreeNode, 0)
queue = append(queue, root)
ans := root.Val
for head := 0; head < len(queue); {
// 在加入下一层之前固定本层节点数量
size := len(queue) - head
for i := 0; i < size; i++ {
node := queue[head]
head++
if i == 0 {
// 当前层第一个访问到的节点就是这一层最左节点。
ans = node.Val
}
// 左孩子先入队，维持下一层从左到右
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
}
}
return ans
}
复杂度分析
- 时间复杂度：$O(n)$，每个节点入队并处理一次。
- 空间复杂度：Java 的双端队列为 $O(w)$，
w是最大层宽；Go 的切片只移动头下标，仍保留已处理项，占 $O(n)$。
关键点总结
[!green]
- 层大小要在加入下一层节点前固定。
- 左孩子必须先于右孩子进入队列。
- 每层只更新一次答案，后处理的更深层覆盖前面的候选。
易错点总结
[!yellow]
- 循环中不断用增长后的队列长度作本层界限，会混入下一层。
- 每个出队节点都覆盖答案，会留下本层最右节点。
- 将 Go 头下标前进当成释放旧切片元素，会低估空间。
- 一直沿左孩子向下只能找到某条分支，无法保证到达最深一层；左右子树中的节点都要入队。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 199. 二叉树的右视图 | 中等 | 同样利用每层顺序选边界节点，本题保留最深层最左值，原题逐层保留最右值。 |
| 102. 二叉树的层序遍历 | 中等 | 复用分层BFS；本题只记录每层首个节点并让后续更深层覆盖。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！