LeetCode LCR 045. 找树左下角的值
题目描述
题意分析
在非空二叉树中，先选择最深的一层，再返回这一层从左到右的第一个节点值。最左指同层位置，最深节点也可能位于右子树，不能只沿左孩子查找。
解法：BFS 记录每层首节点
核心思路
[!blue]
按从上到下的顺序做 BFS，每一层只记录第一个节点的值。更深的层会在后面处理，因此用新的层首值覆盖
answer；最后一次覆盖来自最深层，自然就是所求答案。为保证队首确实是这一层最左节点，每次处理父节点时先加入左孩子，再加入右孩子。当前层父节点本来就按从左到右排列，逐个追加它们的左右孩子后，下一层仍按从左到右排列；缺失孩子直接跳过，不影响剩余节点的相对顺序。
每层开始时先固定队列长度，本轮只弹出这个数量的节点。新加入的下一层节点排在队尾，留到下一轮；本轮下标
i == 0的节点就是该层第一个节点，只在此时覆盖答案。题目保证树非空，所以根所在的第一层一定会更新
answer。代码中的初始值-1只是占位，不表示节点值的大小或是否找到答案；只有根节点时，最后返回的就是根值。
解题步骤
- 将根入队，创建答案变量。
- 每层开始时记录当前队列长度。
- 按固定次数弹出节点，仅用第一个节点值更新答案。
- 将每个节点的非空左孩子、右孩子依次加入队尾。
- 队列耗尽后返回答案，此时保留的是最后一层的首节点值。
代码实现
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$ 为最大层宽，队列最多保存相邻两层的部分节点；除队列外只保存常数个变量。
关键点总结
[!green]
- 从上到下处理层，让更深的层首覆盖先前结果。
- 先左后右加入孩子，保证下一层的队首最靠左。
- 固定本层数量，才能让“本轮第一个节点”对应这一层的最左位置。
易错点总结
[!yellow]
- 只沿左孩子走到底，可能忽略右子树中更深的节点。
- 当前写法只记录层首，若先右后左入队，得到的会是层内另一侧的节点。
- 每个节点都覆盖答案，会保留该层最后一个节点，而不是第一个。
- 在内层循环中使用不断变化的队列长度，会破坏层边界。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 199. 二叉树的右视图 | 中等 | 同样利用每层顺序选边界节点，本题保留最深层最左值，原题逐层保留最右值。 |
| 102. 二叉树的层序遍历 | 中等 | 复用分层BFS；本题只记录每层首个节点并让后续更深层覆盖。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！