统计二叉树中好节点的数目 图解题解
从根走到某个节点，路上有没有人比它更大？
登山时随身带一块「沿途最高海拔」的记录牌：每到一处，如果当前高度不低于牌上的记录，这个点就值得打卡；打完卡再把记录更新成更大值，继续往下传给后面的路段。DFS 下树时带着路径最大值，到了哪个节点就比一比——它自己就是「沿途不曾被超越」的好节点。
这道题到底在问什么
- 示例
- root=[3,1,4,3,null,1,5] → 4
最优解：一步一步想明白
- 3每到一个节点再回头看祖先会重复。
- 4DFS 时带着 pathMax，节点值 ≥ pathMax 就计数，并把新的最大值传给孩子。
- 5带着「这条路径的最大值」往下递归；当前值 ≥ path_max 就是好节点。
- 6根是路径起点、没有祖先，自己就是路径最大值，必然好节点。计数 1。
- 7走到左子 1，路径最大仍是 3；1 比 3 小 → 路上有人挡着，不算好节点。
- 8深入到这个 3，路径最大还是 3，3 ≥ 3 → 好节点。相等也算好，计数 2。
- 9回到根的右子 4，4 ≥ 3 → 好节点，计数 3；并把 path_max 更新成 4 带给它的子树。
- 12一句话记住：DFS 时带着 pathMax，节点值 ≥ pathMax 就计数，并把新的最大值传给孩子。
- 154 的右子 5 ≥ 4 → 好（计数 4），左子 1 ＜ 4 → 不是。关键：path_max 是「每条根→当前的路径」各自的最大值，换分支要用该分支的值、不能用全局最大。答案 ＝ 4。
- 22这题学完别乱跳，去 /leetcode-animation/ds?k=tree 连刷同类树形 DFS；卡住时用 AI 答疑问「path_max 该怎么随递归下传」。
⚠️ 容易写错的地方
✗ 错：用「全局最大值」判断好节点
✓ 对：用「从根到当前这条路径」的最大值 path_max
好节点只看祖先链，不看别的分支；path_max 随递归下传，换分支天然隔离。
✗ 错：判断写成 node.val ＞ path_max
✓ 对：用 node.val ≥ path_max（相等也算好）
题意是「路径上不存在比它大的」，等于路径最大值时仍是好节点。
✗ 错：漏掉根节点
✓ 对：初始 path_max=root.val，根 ≥ 自己
根没有祖先，自己就是路径最大，必然好节点。
完整代码（Python / C++ / Java）
Python
class Solution:
def goodNodes(self, root):
def dfs(node, path_max):
if not node:
return 0
good = 1 if node.val >= path_max else 0
path_max = max(path_max, node.val)
return good + dfs(node.left, path_max) + dfs(node.right, path_max)
return dfs(root, root.val)C++
class Solution {
public:
int goodNodes(TreeNode* root) {
return dfs(root, root->val);
}
int dfs(TreeNode* node, int pathMax) {
if (!node) return 0;
int good = node->val >= pathMax ? 1 : 0;
pathMax = max(pathMax, node->val);
return good + dfs(node->left, pathMax) + dfs(node->right, pathMax);
}
};Java
class Solution {
public int goodNodes(TreeNode root) {
return dfs(root, root.val);
}
private int dfs(TreeNode node, int pathMax) {
if (node == null) return 0;
int good = node.val >= pathMax ? 1 : 0;
pathMax = Math.max(pathMax, node.val);
return good + dfs(node.left, pathMax) + dfs(node.right, pathMax);
}
}套路模板 · 路径最大值 DFS 骨架
# 路径最大值 DFS 骨架
def dfs(node, path_max):
if not node: return 0
good = 1 if node.val >= path_max else 0 # ≥ 即好节点
path_max = max(path_max, node.val) # 更新后下传
return good + dfs(node.left, path_max) + dfs(node.right, path_max)
return dfs(root, root.val) # 初值=根，根必好复杂度
时间复杂度
O(n)
每个节点恰好访问一次
空间复杂度
O(h)
递归栈深度＝树高 h（最坏退化成链 O(n)）
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 统计二叉树中好节点的数目 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
整体思路是什么？+
一次 DFS，参数带上「从根到当前路径的最大值」path_max。每到一个节点：若 node.val ≥ path_max 则它是好节点（计数+1），再用 max(path_max, node.val) 更新后递归左右子树。累加所有好节点数。
这道题为什么用「树」，换最直接的暴力解会差在哪？+
树抓住了本题的结构特征，把暴力解里重复的工作省掉；暴力解通常要多嵌套一层枚举，数据一大就超时。具体对比见上文「暴力解及其卡点」与「最优解逐步推演」两节。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。