LeetCode 1448中等树
统计二叉树中好节点的数目 图解题解
从根走到某个节点，路上有没有人比它更大？
登山时随身带一块「沿途最高海拔」的记录牌：每到一处，如果当前高度不低于牌上的记录，这个点就值得打卡；打完卡再把记录更新成更大值，继续往下传给后面的路段。DFS 下树时带着路径最大值，到了哪个节点就比一比——它自己就是「沿途不曾被超越」的好节点。
这道题到底在问什么
给定一棵二叉树，若从根到节点 X 的路径上不存在比 X 值更大的节点，则 X 是「好节点」（X 自身可以等于路径最大值）。根节点必为好节点。返回好节点的总数。
- 输入
- root=[3,1,4,3,2,1,5,1,6,null,null,6,5,null,5]
- 输出
- 8
最优解：一步一步想明白
- 3做法干净利落：DFS 时给每个节点带一个参数 pathMax = 根到它父亲这一路的最大值。进入节点时比一下：如果 当前值 ≥ pathMax，说明来路上没有比它大的，它就是好节点，计数 +1；然后把 pathMax 更新成 max(pathMax, 当前值) 传给左右孩子。下面逐节点看这趟 DFS。
- 4DFS 起点 = 根 3，pathMax 初始 = −∞先看清这棵树：根是 3。接下来从根出发做 DFS——每进入一个节点，拿它的值和「根到这里的路径最大值」比一比：不比它小就是好节点。然后更新路径最大值往下传，子树探完就回溯。我们边走边数。
- 5计数 +1 → 1；路径最大值更新为 3从根 3 出发。根上方没有任何节点，路径最大值初始是 −∞，所以 3 ≥ −∞ 一定成立——根永远是好节点，计数变成 1。接着把路径最大值更新为 3 传给孩子，往下深入。
- 6计数不变 = 1；路径最大值仍为 3走到节点 1，它扛的路径最大值是 3。1 小于 3，说明根到它的路上有比它大的节点，所以它不是好节点，计数保持 1。路径最大值仍是 3，继续往它的子树探。
- 7计数 +1 → 2；路径最大值更新为 3深度优先走到节点 3。看它身上扛的「根到这里的路径最大值」是 3，而 3 ≥ 3 成立——路径上没有比它大的，它是好节点！计数 +1 = 2。再把路径最大值更新成 max(3, 3) = 3 继续往下传。
- 8计数不变 = 2；路径最大值仍为 3走到节点 1，它扛的路径最大值是 3。1 小于 3，说明根到它的路上有比它大的节点，所以它不是好节点，计数保持 2。路径最大值仍是 3，继续往它的子树探。
- 9子树探完；路径最大值退回 3节点 1 的整棵子树已经探完，回溯：把它从当前路径弹出，路径最大值退回到进它之前的 3（这样它的兄弟分支用的是正确的祖先最大值，不会被这一侧影响），并标蓝表示「这块走过了」。回到节点 3，继续它的另一条岔路。
- 10计数 +1 → 3；路径最大值更新为 6深度优先走到节点 6。看它身上扛的「根到这里的路径最大值」是 3，而 6 ≥ 3 成立——路径上没有比它大的，它是好节点！计数 +1 = 3。再把路径最大值更新成 max(3, 6) = 6 继续往下传。
- 11子树探完；路径最大值退回 3节点 6 的整棵子树已经探完，回溯：把它从当前路径弹出，路径最大值退回到进它之前的 3（这样它的兄弟分支用的是正确的祖先最大值，不会被这一侧影响），并标蓝表示「这块走过了」。回到节点 3，继续它的另一条岔路。
- 12子树探完；路径最大值退回 3节点 3 的整棵子树已经探完，回溯：把它从当前路径弹出，路径最大值退回到进它之前的 3（这样它的兄弟分支用的是正确的祖先最大值，不会被这一侧影响），并标蓝表示「这块走过了」。回到节点 1，继续它的另一条岔路。
- 13计数不变 = 3；路径最大值仍为 3走到节点 2，它扛的路径最大值是 3。2 小于 3，说明根到它的路上有比它大的节点，所以它不是好节点，计数保持 3。路径最大值仍是 3，继续往它的子树探。
- 14子树探完；路径最大值退回 3节点 2 的整棵子树已经探完，回溯：把它从当前路径弹出，路径最大值退回到进它之前的 3（这样它的兄弟分支用的是正确的祖先最大值，不会被这一侧影响），并标蓝表示「这块走过了」。回到节点 1，继续它的另一条岔路。
- 15子树探完；路径最大值退回 3节点 1 的整棵子树已经探完，回溯：把它从当前路径弹出，路径最大值退回到进它之前的 3（这样它的兄弟分支用的是正确的祖先最大值，不会被这一侧影响），并标蓝表示「这块走过了」。回到节点 3，继续它的另一条岔路。
- 16计数 +1 → 4；路径最大值更新为 4深度优先走到节点 4。看它身上扛的「根到这里的路径最大值」是 3，而 4 ≥ 3 成立——路径上没有比它大的，它是好节点！计数 +1 = 4。再把路径最大值更新成 max(3, 4) = 4 继续往下传。
- 17计数不变 = 4；路径最大值仍为 4走到节点 1，它扛的路径最大值是 4。1 小于 4，说明根到它的路上有比它大的节点，所以它不是好节点，计数保持 4。路径最大值仍是 4，继续往它的子树探。
- 18计数 +1 → 5；路径最大值更新为 6深度优先走到节点 6。看它身上扛的「根到这里的路径最大值」是 4，而 6 ≥ 4 成立——路径上没有比它大的，它是好节点！计数 +1 = 5。再把路径最大值更新成 max(4, 6) = 6 继续往下传。
- 19子树探完；路径最大值退回 4节点 6 的整棵子树已经探完，回溯：把它从当前路径弹出，路径最大值退回到进它之前的 4（这样它的兄弟分支用的是正确的祖先最大值，不会被这一侧影响），并标蓝表示「这块走过了」。回到节点 1，继续它的另一条岔路。
- 20计数 +1 → 6；路径最大值更新为 5深度优先走到节点 5。看它身上扛的「根到这里的路径最大值」是 4，而 5 ≥ 4 成立——路径上没有比它大的，它是好节点！计数 +1 = 6。再把路径最大值更新成 max(4, 5) = 5 继续往下传。
- 21子树探完；路径最大值退回 4节点 5 的整棵子树已经探完，回溯：把它从当前路径弹出，路径最大值退回到进它之前的 4（这样它的兄弟分支用的是正确的祖先最大值，不会被这一侧影响），并标蓝表示「这块走过了」。回到节点 1，继续它的另一条岔路。
- 22子树探完；路径最大值退回 4节点 1 的整棵子树已经探完，回溯：把它从当前路径弹出，路径最大值退回到进它之前的 4（这样它的兄弟分支用的是正确的祖先最大值，不会被这一侧影响），并标蓝表示「这块走过了」。回到节点 4，继续它的另一条岔路。
- 23计数 +1 → 7；路径最大值更新为 5深度优先走到节点 5。看它身上扛的「根到这里的路径最大值」是 4，而 5 ≥ 4 成立——路径上没有比它大的，它是好节点！计数 +1 = 7。再把路径最大值更新成 max(4, 5) = 5 继续往下传。
- 24计数 +1 → 8；路径最大值更新为 5深度优先走到节点 5。看它身上扛的「根到这里的路径最大值」是 5，而 5 ≥ 5 成立——路径上没有比它大的，它是好节点！计数 +1 = 8。再把路径最大值更新成 max(5, 5) = 5 继续往下传。
- 25子树探完；路径最大值退回 5节点 5 的整棵子树已经探完，回溯：把它从当前路径弹出，路径最大值退回到进它之前的 5（这样它的兄弟分支用的是正确的祖先最大值，不会被这一侧影响），并标蓝表示「这块走过了」。回到节点 5，继续它的另一条岔路。
- 26子树探完；路径最大值退回 4节点 5 的整棵子树已经探完，回溯：把它从当前路径弹出，路径最大值退回到进它之前的 4（这样它的兄弟分支用的是正确的祖先最大值，不会被这一侧影响），并标蓝表示「这块走过了」。回到节点 4，继续它的另一条岔路。
- 27子树探完；路径最大值退回 3节点 4 的整棵子树已经探完，回溯：把它从当前路径弹出，路径最大值退回到进它之前的 3（这样它的兄弟分支用的是正确的祖先最大值，不会被这一侧影响），并标蓝表示「这块走过了」。回到节点 3，继续它的另一条岔路。
- 28子树探完；路径最大值退回 −∞节点 3 的整棵子树已经探完，回溯：把它从当前路径弹出，路径最大值退回到进它之前的 −∞（这样它的兄弟分支用的是正确的祖先最大值，不会被这一侧影响），并标蓝表示「这块走过了」。整棵树都探完了。
- 29好节点：3,3,6,4,6,5,5,5 → 8 个整棵树走完，把所有好节点标绿：它们的值是 3, 3, 6, 4, 6, 5, 5, 5，共 8 个。每一个都满足「从根到它的路上没有比它大的」。注意非好节点（如路上撞到过更大的祖先）不计入。答案 = 8。
⚠️ 容易写错的地方
✗ 错：拿当前值跟整棵树最大值比
✓ 对：只跟「根到它」这条路径上的最大值比
好节点是相对来路而言，不是相对全局
✗ 错：判定用 val > pathMax（严格大于）
✓ 对：用 val ≥ pathMax（允许相等）
等于路径最大值也算好节点，根本身就是例子
✗ 错：根的 pathMax 初值随便设 0
✓ 对：设成 −∞（INT_MIN）
有负值节点时设 0 会漏判根/小值节点
完整代码（Java / Python / C++）
Java
class Solution {
public int goodNodes(TreeNode root) {
return dfs(root, Integer.MIN_VALUE); // 根上方无节点，max 取最小
}
private int dfs(TreeNode node, int pathMax) {
if (node == null) return 0; // 空节点：0 个好节点
int good = node.val >= pathMax ? 1 : 0; // 不比路径最大值小 → 好节点
int nextMax = Math.max(pathMax, node.val); // 把最大值带给子树
good += dfs(node.left, nextMax); // 左子树的好节点数
good += dfs(node.right, nextMax); // 右子树的好节点数
return good;
}
}Python
class Solution:
def goodNodes(self, root: TreeNode) -> int:
def dfs(node, path_max):
if not node: # 空节点：0 个
return 0
good = 1 if node.val >= path_max else 0 # 不比路径最大值小 → 好节点
nxt = max(path_max, node.val) # 把最大值带给子树
good += dfs(node.left, nxt)
good += dfs(node.right, nxt)
return good
return dfs(root, float('-inf')) # 根上方无节点C++
class Solution {
public:
int goodNodes(TreeNode* root) {
return dfs(root, INT_MIN); // 根上方无节点，max 取最小
}
int dfs(TreeNode* node, int pathMax) {
if (!node) return 0; // 空节点：0 个
int good = node->val >= pathMax ? 1 : 0; // 不比路径最大值小 → 好节点
int nextMax = max(pathMax, node->val); // 把最大值带给子树
good += dfs(node->left, nextMax);
good += dfs(node->right, nextMax);
return good;
}
};复杂度
时间
O(n)
每个节点恰好访问一次
空间
O(h)
递归栈深 = 树高 h；最坏(链)O(n)，平衡 O(log n)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 统计二叉树中好节点的数目 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这道题为什么用「树」，换最直接的暴力解会差在哪？+
树抓住了本题的结构特征，把暴力解里重复的工作省掉；暴力解通常要多嵌套一层枚举，数据一大就超时。具体对比见上文「暴力解及其卡点」与「最优解逐步推演」两节。
时间复杂度为什么是 undefined？怎么推出来的？+
按上文复杂度小节的推导，时间复杂度为 undefined。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 统计二叉树中好节点的数目 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。