LeetCode 1448. 统计二叉树中好节点的数目

2026-07-14 HGNULB 约 11 分钟

文章信息 3 个分类 4 个标签

分类

题目描述

✅ 1448. 统计二叉树中好节点的数目

题意分析

题目给定一棵二叉树的根节点 root，要求统计「好节点」的数目。节点 X 是好节点，当且仅当从根到 X 的这条路径上不存在比 X 的值更大的节点。根节点的路径上只有它自己，所以根节点永远是好节点，答案至少是 1。

第一个关键观察是：判定某个节点是否为好节点，并不需要知道根到它的整条路径，只需要知道这条路径上的最大值这一个标量。因为「不存在比 X 更大的节点」这句话只关心路径里的最大者，路径的具体构成、长度、节点顺序都不改变结论。这就把一个看起来依赖「整条路径」的判定压缩成了依赖一个数——这是本题所有解法的共同前提。

第二个关键观察是把自然语言改写成不等式：「路径上不存在比 X 更大的节点」等价于「路径最大值不大于 X 的值」，也就是「X 的值 ≥ 路径最大值」。等号必须包含在内：路径上出现与 X 相等的值时，那个值并不比 X 更大，所以 X 依然是好节点。官方样例 root = [3,1,4,3,null,1,5] 就专门埋了这个点——左子树末端那个 3 与根的 3 相等，它正是被计入的四个好节点之一。若把判定写成严格大于，这个节点会被漏掉。

边界情形有三处需要留意。其一，树至少有一个节点，不存在空树，root = [1] 的答案是 1；但递归实现里仍然需要处理空孩子。其二，节点值可以是负数，因此「路径最大值」的初始值绝对不能取 0，否则整棵树全为负值时连根节点都会被误判成非好节点；正确做法是取一个比任何节点值都小的哨兵，让「空路径的最大值」等于取最大值运算的单位元。其三，节点值允许重复，兄弟之间、祖孙之间都可能相等，判定必须容纳这种情况。

约束还透露了一个信号：节点数量可以达到十万量级。这意味着不能对每个节点都重新回溯一次到根、扫一遍路径求最大值，那样的代价是节点数乘以树高；判定所需的信息必须在一次遍历中顺带维护出来。

解法：DFS 携带路径最大值

核心思路

既然判定只依赖「根到当前节点这条路径上的最大值」这一个标量，那就让这个标量跟着遍历一起往下走。递归函数除了当前节点，再多带一个参数 pathMax，并把它的含义写死为一条不变量：进入某个节点时，pathMax 恰好等于根到该节点父节点这条路径上的最大值。整个解法的正确性都挂在这一句上。

不变量的成立可以用归纳法说明。基础情形是根节点：它没有父节点，对应的路径为空，于是取一个比所有节点值都小的哨兵作为「空路径的最大值」，判定 root.val >= 哨兵 必然成立，与「根永远是好节点」正好吻合，不需要为根另写特例分支。归纳步骤是：若进入节点 X 时不变量成立，那么根到 X 的路径最大值就是 max(pathMax, X.val)；把这个值作为参数传给 X 的两个孩子，孩子进入时的不变量同样成立。于是整棵树上每个节点拿到的 pathMax 都是正确的，每个节点的判定也就都是正确的。

这个设计的价值在于把代价从 $O(n \times h)$ 压到 $O(n)$。朴素做法是对每个节点单独往上回溯到根、扫一遍路径取最大值，单次花 $O(h)$，总共 $O(n \times h)$。而路径最大值在父子之间只差一次取最大值运算，是一个可以增量维护的聚合量——父节点的结果加上当前节点的值，常数时间就能算出子节点该看到的值。既然如此，自上而下传递一次就够了，每个节点只被访问一次，那些重复的路径扫描全部消失。

之所以用参数传递而不是「全局变量加回溯」，是因为参数天然带有作用域。X 的左子树递归里对 pathMax 的任何更新都留在那次调用的栈帧内，返回到 X 之后不会影响右子树看到的值。若改用一个全局的 max 字段，就必须在递归返回时手动把它恢复成进入前的样子；这是一处必须记得写、又不写也能编译通过的对称操作，一旦漏掉，右子树会错误地继承左子树留下的最大值，答案偏小。参数传递把「恢复现场」这件事交给了语言的调用栈，直接消灭了一类出错可能。

计数同样用返回值而不是全局累加：让递归函数返回「以当前节点为根的子树中好节点的数目」，它等于当前节点自身贡献的 0 或 1，加上左右子树的返回值。这样每个函数的语义自洽，单独拿出来也能验证。顺便一提，同一条不变量换成显式栈或队列也完全成立——只要把节点和它对应的 pathMax 成对入队即可，所以标签里的广度优先搜索并不是另一种思路，而是同一思路的另一种遍历顺序；遍历顺序不影响结果，因为每个节点的判定只与它的祖先有关，与兄弟节点无关。

解题步骤

定义递归函数 dfs(node, pathMax)，返回以 node 为根的子树里好节点的数目，参数 pathMax 的含义固定为「根到 node 父节点这条路径上的最大值」。含义必须一开始就定死，否则后面每一步都会含混，也没法判断边界该填什么。

写递归出口：node 为空时返回 0。空节点不是节点，不参与计数；把出口放在函数开头，调用方就不必在递归前逐个判断孩子是否存在，两侧孩子可以无条件递归。

判定当前节点：若 node.val >= pathMax 则当前节点是好节点，贡献 1，否则贡献 0。这里用 >= 而不是 >，因为路径上与它相等的值并不比它更大。

计算传给孩子的新最大值 newMax = max(pathMax, node.val)。它就是根到当前节点这条路径的最大值，也正是孩子进入时应当看到的 pathMax，不变量靠这一行逐层传递下去。

用同一个 newMax 分别递归左右孩子，把两个返回值与当前节点的贡献相加后返回。两棵子树共用同一个 newMax、互不干扰，这正是参数传递替代手工回溯的地方。

顶层用一个比任何节点值都小的哨兵调用 dfs(root, 哨兵)，把结果直接返回。哨兵让根节点的判定自动为真，省掉一个特例分支。

以 root = [3,1,4,3,null,1,5] 走一遍：这棵树的根是 3，它的左孩子是 1、右孩子是 4；1 的左孩子是 3、右孩子为空；4 的左孩子是 1、右孩子是 5，一共七个节点。顶层调用 dfs(根 3, 哨兵)，根收到的 pathMax 是哨兵，3 >= 哨兵 成立，计数（累计 1），向下传 newMax = 3。左孩子 1 收到 pathMax = 3，1 >= 3 不成立，不计数，向下传 newMax = max(3, 1) = 3。它的左孩子 3 收到 pathMax = 3，3 >= 3 成立，计数（累计 2）——这就是等号在起作用的地方，若判定写成严格大于，这个节点会被漏掉。回到根的右分支：4 收到 pathMax = 3，4 >= 3 成立，计数（累计 3），向下传 newMax = 4；4 的左孩子 1 收到 pathMax = 4，1 >= 4 不成立，不计数；右孩子 5 收到 pathMax = 4，5 >= 4 成立，计数（累计 4），向下传 newMax = 5。七个节点里被计数的是根 3、左分支末端的 3、4、5 共四个，答案 4，与样例一致。

再用一棵全是相等值的小树 root = [5,5,5] 单独说明等号的作用：根 5 对哨兵成立，计数并下传 newMax = 5；两个孩子都收到 pathMax = 5，5 >= 5 成立，各自计数。答案是 3，三个节点全是好节点。若把判定误写成 node.val > pathMax，两个孩子都会被判成非好节点，只剩根节点被计入，答案变成 1。

代码实现

class Solution {
    public int goodNodes(TreeNode root) {
        // 根节点没有祖先，用比任何节点值都小的哨兵作初始路径最大值，保证根一定被计入
        return dfs(root, Integer.MIN_VALUE);
    }

    // pathMax：根到 node 父节点这条路径上的最大值（不变量）
    private int dfs(TreeNode node, int pathMax) {
        if (node == null) {
            return 0; // 空节点不是节点，不参与计数
        }
        // 「路径上不存在更大的值」等价于当前值不小于路径最大值，等号必须保留
        int count = node.val >= pathMax ? 1 : 0;
        int newMax = Math.max(pathMax, node.val); // 下传前更新为根到当前节点的最大值
        count += dfs(node.left, newMax); // 两棵子树共用同一个 newMax，互不干扰
        count += dfs(node.right, newMax);
        return count; // 返回以 node 为根的子树中好节点的数目
    }
}

func goodNodes(root *TreeNode) int {
    // pathMax：根到 node 父节点这条路径上的最大值（不变量）
    var dfs func(node *TreeNode, pathMax int) int
    dfs = func(node *TreeNode, pathMax int) int {
        if node == nil {
            return 0 // 空节点不是节点，不参与计数
        }
        count := 0
        if node.Val >= pathMax { // 等号必须保留：路径上有相等值时当前节点仍是好节点
            count = 1
        }
        newMax := pathMax
        if node.Val > newMax {
            newMax = node.Val // 下传前更新为根到当前节点的最大值
        }
        count += dfs(node.Left, newMax) // 两棵子树共用同一个 newMax，互不干扰
        count += dfs(node.Right, newMax)
        return count // 返回以 node 为根的子树中好节点的数目
    }
    // 根节点没有祖先，用比任何节点值都小的哨兵作初始路径最大值
    return dfs(root, -1<<31)
}

复杂度分析

时间复杂度：$O(n)$，其中 n 为节点数。每个节点恰好被访问一次，在它身上只做一次比较、一次取最大值和两次递归调用，全是常数代价，不存在任何重复扫描祖先路径的动作。

空间复杂度：$O(h)$，其中 h 为树高。算法不申请额外容器，占用只来自递归调用栈，而栈的深度等于当前节点在树中的深度，最深为 h。树平衡时 h 为 $O(\log n)$；最坏情况是一条斜树，此时 h 等于 n，空间退化为 $O(n)$。

关键点总结

若子问题的判定只依赖祖先路径上的某个聚合量（最大值、和、异或、计数……），就把这个聚合量作为参数自上而下传递，而不是在每个节点重新扫一遍路径。这一步通常直接把 $O(n \times h)$ 降到 $O(n)$，是树上「路径类」问题最高频的优化。

判断一个聚合量能否这样传递，标准是它是否可增量维护：从父节点的值出发，常数时间就能算出子节点该看到的值。最大值、和、位运算都满足；「路径上第二大的值」这类就不满足，需要携带更多状态。

需要「进入子树时生效、离开子树时失效」的状态，优先用函数参数承载，让调用栈替你恢复现场，而不是用全局变量加手工回溯。后者多出一处必须记得写、漏写却仍能编译的对称操作。

把自然语言约束改写成不等式时，先定死等号落在哪一侧：「不存在比它更大的」是 ≥，「严格大于所有」才是 >。这一步读错是这类题最常见的错误来源，而且往往能通过大部分用例。

给递归参数写下一句精确的不变量（「进入时该参数等于……」），并单独检查根节点这个初始情形是否满足。不变量一旦成立，正确性就由归纳法保证，不必逐个用例去试。

「空集合的聚合值」应当取该运算的单位元：求和取 0，取最大值取负无穷，取最小值取正无穷。只有在确知取值非负时，最大值的初始值取 0 才恰好等价。

易错点总结

判定写成严格大于 node.val > pathMax：root = [3,1,4,3,null,1,5] → 左分支末端与根相等的那个 3 被漏掉，输出 3，正确答案是 4；在全等值的 root = [5,5,5] 上退化得更彻底，只有根被计入，输出 1，正确答案是 3。

路径最大值的初始值取 0：root = [-1,-2,-3] → 根的判定 -1 >= 0 不成立，连根节点都不计数，输出 0，正确答案是 1；root = [-2,-3,-1] 输出 0，正确答案是 2。只要树里混有负数就可能出错，root = [-5,-10,3,-20,null,1,7] 输出 2，正确答案是 3。

递归时忘记更新最大值，把自己收到的 pathMax 原样传给孩子：root = [3,1,4,3,null,1,5] → 所有节点都只跟哨兵或根值比较，深层那个 1 也被算成好节点，输出 6，正确答案是 4。

只和父节点的值比较，而不是和整条路径的最大值比较：root = [5,1,null,4,null,null,6]（一条 5 → 1 → 4 → 6 的链）→ 4 >= 1 被判成好节点，可它的祖先 5 比它更大，输出 3，正确答案是 2。

用全局变量记录路径最大值，但递归返回时不恢复：root = [2,5,1,null,null,3,null] → 左子树把全局最大值抬到 5，右分支的 3 拿这个被污染的值去比较而被判成非好节点，输出 2，正确答案是 3。

只在叶子节点处统计，把「好节点」误当成根到叶的路径问题：root = [3,1,4,3,null,1,5] → 中间层的好节点（根 3 和 4）全部丢失，输出 2，正确答案是 4。

把初始 pathMax 设成 root.val 之后仍用严格大于判定：root = [1] → 根的判定 1 > 1 不成立，输出 0，正确答案是 1；root = [3,3,null,4,2] 输出 1，正确答案是 3。初始值取哨兵还是取根值都可以，但必须与判定符号配套。

漏掉 node == null 的递归出口，又无条件递归两侧孩子：任何存在单侧孩子的树都会触发，例如 root = [3,3,null,4,2] → 递归到空孩子时解引用空指针，Java 抛出 NullPointerException，Go 触发 invalid memory address or nil pointer dereference panic，程序直接崩溃而不是给出答案。

相似题目

题目	难度	考察点
104. 二叉树的最大深度	简单	信息自底向上从子树汇总到根，与本题自上而下携带祖先信息方向相反
112. 路径总和	简单	同样下传一个标量（剩余目标值），但只判定「是否存在」，可以在找到后提前短路返回
113. 路径总和 II	中等	要求输出完整路径，必须显式维护路径列表并在返回时弹出，无法压缩成单个标量
129. 求根节点到叶节点数字之和	中等	下传的聚合量是路径拼成的数字，且只在叶子处结算并累加，中间节点不贡献答案
437. 路径总和 III	中等	路径起点不限于根，需要用前缀和配合哈希表统计任意祖先作起点的方案数
988. 从叶结点开始的最小字符串	中等	下传的是字符路径，比较发生在叶子处，还要在多条路径结果之间取字典序最小
1372. 二叉树中的最长交错路径	中等	状态需区分「上一步来自左还是右」，靠自底向上返回二元状态的树形 DP 求解