LeetCode 1448. 统计二叉树中好节点的数目
题目描述
题意分析
一个节点是好节点，当且仅当从根到它的整条路径上，没有任何节点值比它更大。需要统计这样的节点总数，路径中的值与当前值相等时仍然符合条件。
比较范围仅是当前节点自己的祖先路径，不包括其他分支。根节点没有祖先，因此必然是好节点；节点值可能为负，不能把路径最大值默认成零。
解法：DFS 下传当前祖先最大值
核心思路
[!blue]
判断当前节点时，不需要重新扫描整条祖先路径，只需知道祖先里的最大值。定义递归参数
pathMax为从根到当前节点父亲的最大值；若node.val >= pathMax，就表示不存在更大的祖先，当前节点贡献一个好节点。继续处理孩子前，计算
newMax = max(pathMax, node.val)，使传下去的状态包含当前节点。这样每个子调用收到的仍是它全部祖先的最大值，同一个状态定义可以逐层重复使用。左右子树都应从相同的父路径状态开始。
newMax是按值传递的整数，左子树内部产生的更大值只影响左边后代，不会改动右子树收到的参数，因此无需额外回溯恢复，也不能用全树共享的最大值替代它。当前节点不是好节点，也不能停止搜索：后代仍可能出现足够大的值，重新达到祖先最大值。因此每个非空节点都要递归两个孩子，把当前贡献与左右子树返回的计数相加。空节点返回零；根使用小于题目所有节点值的哨兵，统一处理没有祖先的情况。
解题步骤
- 从根开始递归，将最小整数作为初始祖先最大值。
- 当前节点为空时返回零；否则比较当前值与
pathMax，决定本节点贡献零还是一。- 计算包含当前值的新路径最大值，分别传给左右孩子。
- 将左右子树计数和当前贡献相加并返回，最外层得到全树答案。
代码实现
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);
// 两棵子树共用同一个 newMax，互不干扰
count += dfs(node.left, newMax);
count += dfs(node.right, newMax);
// 返回以 node 为根的子树中好节点的数目
return count;
}
}
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
}
// 两棵子树共用同一个 newMax，互不干扰
count += dfs(node.Left, newMax)
count += dfs(node.Right, newMax)
// 返回以 node 为根的子树中好节点的数目
return count
}
// 根节点没有祖先，用比任何节点值都小的哨兵作初始路径最大值
return dfs(root, -1<<31)
}
复杂度分析
- 时间复杂度：$O(n)$，每个节点访问一次，判断与更新最大值都是常数操作。
- 空间复杂度：$O(h)$，
h为树高，来自递归调用栈；平衡树为 $O(\log n)$，退化为链时为 $O(n)$。
关键点总结
[!green]
- 祖先路径的所有比较可以压缩成一个最大值，不必重复扫描路径。
- 当前判断使用祖先最大值，下传给孩子前再包含当前节点。
- 左右分支各自持有路径状态，避免跨分支污染。
- 当前不合格不代表整棵子树都不合格，仍需遍历后代。
易错点总结
[!yellow]
- 使用严格大于判断，会漏掉与祖先最大值相等的好节点。
- 用全树最大值或遍历至今最大值判断，会让其他分支错误限制当前路径。
- 初始最大值设为零，会误判负数根以及只包含负值的路径。
- 传给孩子时没有纳入当前节点，会遗漏当前节点对后代的限制。
- 遇到坏节点就剪枝，会丢掉它下面可能出现的好节点。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 112. 路径总和 | 简单 | 同样DFS携带从根到当前位置的路径状态，原题携带剩余目标和，本题携带路径最大值。 |
| 1026. 节点与其祖先之间的最大差值 | 中等 | 同样沿根路径携带极值，原题同时保留最大、最小值计算祖先差。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！