LeetCode 513. 找树左下角的值

2022-08-01 HGNULB 约 6 分钟

文章信息 11 个分类 5 个标签

分类

LeetCode CodeTop 中等已解决已掌握 5-10 字节跳动微软阿里巴巴滴滴虾皮

题目描述

✅ 513. 找树左下角的值

题意分析

输入是一棵二叉树的根节点，要求返回「最底层最靠左」的那个节点的值。

这句话要拆成两层含义：先确定哪一层是最深的一层，再在那一层里取最左边的节点。注意「最左」指的是这一层从左往右数的第一个节点，而不是「沿着左指针一直走到底」——最深层的第一个节点完全可能是某个节点的右孩子。

同样地，答案也不一定是「深度最大的叶子」中位置最靠前的那个，因为最深层里的节点必然都是叶子，但判断标准始终是「层内最靠左」，而不是先筛叶子。

约束里节点数在 1 到 $10^4$ 之间，所以树非空，不必处理根为空的情形；节点值可以是负数，不能用特殊值表示「还没找到」。边界上要覆盖：只有根节点时答案就是根值；整棵树退化成一条右链时，最深层唯一的那个节点就是答案。

解法：层序遍历记录每层第一个节点

核心思路

题目要求先满足“深度最大”，再满足“同层最左”。层序遍历恰好按深度从小到大访问节点；只要同层保持从左到右的顺序，每层第一个出队的节点就是该层最左节点。逐层覆盖答案，最后留下的自然属于最深层。

队列的分层不变量是：每轮开始时，队列前 size 个节点恰好是当前层，并且按从左到右排列。初始队列只有根节点，不变量成立；处理一层时按先左孩子、后右孩子入队，下一层仍保持从左到右的相对顺序。固定 size 后，本轮不会误处理刚入队的下一层节点。

每处理完一层，ans 就等于已处理的最深层最左值。遍历结束时所有层都已处理，因此 ans 是整棵树最底层的最左值，既不会取到浅层节点，也不会被同层靠右节点覆盖。

DFS 也利用同一个顺序事实：先访问左子树，并且只在第一次到达更深层时更新答案。这样每个深度首次访问到的节点必是该层最左节点。这里选择 BFS，是因为“按层取第一个”的代码和题意最直接。

解题步骤

将根节点入队，并用根值初始化 ans。题目保证根节点非空。

每轮先记录当前队列长度 size，它就是当前层的节点数。

依次弹出这 size 个节点；当下标为 0 时，用该节点值覆盖 ans。

对每个节点按左、右顺序将非空孩子入队，维持下一层从左到右的顺序。

队列为空后返回 ans，最后一次覆盖一定来自最深层。

例如 root = [1,2,3,null,null,4,5]：各层依次为 [1]、[2,3]、[4,5]，答案依次更新为 1、2、4，最终返回 4。这也说明答案可能位于根的右子树，不能简单沿左指针走到底。

代码实现

import java.util.ArrayDeque;
import java.util.Queue;

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)$。每个节点恰好入队、出队一次。

空间复杂度：$O(w)$，w 是二叉树的最大层宽，最坏为 $O(n)$。

关键点总结

“最底层最左”是有优先级的两个条件：先找最大深度，再取该层第一个节点。

每轮开始必须固定 size，否则新入队的孩子会混入当前层，层边界随即失效。

先左后右入队，保证队列内同层节点始终从左到右排列；每层下标 0 才能代表最左节点。

BFS 的“每层第一个”与左优先 DFS 的“每个深度第一次访问”本质相同，都是利用稳定的访问顺序。

若面试官要求 $O(h)$ 辅助空间，可改写为 DFS；但链状树递归深度为 $O(n)$，仍需说明栈溢出风险。

易错点总结

沿左指针走到底不等于找最深层最左节点；最深节点可能位于根的右子树。

不固定当前层的 size，会把下一层节点提前消费，无法判断每层第一个节点。

先右后左入队会把同层顺序反转，最终得到最深层最右值。

把空孩子也入队会引入空指针，并干扰“下标 0 是最左节点”的判断。

DFS 若用 depth >= maxDepth 更新，同层右侧节点会覆盖答案；必须只在 depth > maxDepth 时更新。

DFS 若先访问右子树，那么每层第一次访问到的是最右节点，必须保持根、左、右的访问顺序。

相似题目

题目	难度	考察点
102. 二叉树的层序遍历	中等	分层模板本身，要输出每一层的完整列表
103. 二叉树的锯齿形层序遍历	中等	奇偶层方向交替，用双端插入避免额外反转
107. 二叉树的层序遍历 II	中等	结果按层自底向上，收集后整体反转或头插
199. 二叉树的右视图	中等	取每层最后一个节点，与本题取第一个恰好对称
LCR 046. 二叉树的右视图	中等	与 199 同题，可对照递归版的「先右后左」写法
LCR 045. 找树左下角的值	中等	本题同题，适合练习递归带深度参数的第二种解法
429. N 叉树的层序遍历	中等	孩子数量不定，入队要遍历孩子列表
515. 在每个树行中找最大值	中等	层内做最大值聚合，注意初值不能设为 0
LCR 044. 在每个树行中找最大值	中等	与 515 同题，可练习用递归按深度下标聚合
637. 二叉树的层平均值	简单	层内求和取平均，需注意整数溢出与浮点精度
662. 二叉树最大宽度	中等	要给节点编号计算跨度，空位也要计入宽度
958. 二叉树的完全性检验	中等	空节点也入队，靠「空之后不能再有非空」做判定
1302. 层数最深叶子节点的和	中等	同样只关心最深层，但要对整层求和而非取首个
剑指 Offer 32 - I. 从上到下打印二叉树	中等	输出摊平成一维数组，不需要分层
剑指 Offer 32 - II. 从上到下打印二叉树 II	简单	与 102 同题，用于确认分层模板已经写熟
剑指 Offer 32 - III. 从上到下打印二叉树 III	中等	与 103 同题的锯齿版本
面试题 04.03. 特定深度节点链表	中等	每层输出改成链表，要在层内维护尾指针