LeetCode 1448，Count Good Nodes in Binary Tree，中文叫统计二叉树中好节点的数目。我第一次在题库里看到这个标题时，觉得无非就是遍历整棵树然后逐个判断，实际写起来也确实是这个思路，但真要把“好节点”的定义用代码干净地表达出来，里面还是有几个容易翻车的细节。本文就从题目定义讲起，把DFS、BFS两种解法都拆一遍，再结合我那次耗时100ms的提交记录，聊聊性能复盘和边界条件的处理。
先说清楚这题适合谁。刚刷完二叉树基础、想练递归状态传递的人，或者准备面试想找个简单题热身的，都可以拿它来试手。它不像中等的树题那样需要复杂剪枝、记忆化，但却是“树上的路径条件统计”这个经典题型的入门代表。把这题吃透，后面再碰路径和、路径最大差值这类变式题会轻松很多。
代码量不多，主解法的核心函数不超过15行，难点在于想明白两点：第一，好节点到底是跟谁比；第二，递归或迭代过程中，那条路径上的“当前最大值”应该以什么形式传递。下面我一个个说。
1. 好节点判定：题意里最容易忽略的两个细节
1.1 什么叫“路径上所有节点的值都不大于当前节点”
题目定义是：对任意一个节点，如果从根节点到它的路径上的所有节点值都不大于这个节点的值，那它就是好节点。
注意这里说的是“路径上所有节点”，不是“父节点”，也不是“左右子树”。很多人第一眼会误解成“当前节点值大于等于父节点值”，比如一棵树 [3,1,4]，1比父节点3小，所以不是好节点；4比父节点3大，确实算好节点。可一旦树深了，单纯跟父节点比就会出错。
我拿一个生活化的例子：想象一条走廊里站了一排人，每个人手里举着一块数字牌。某个人要被称为“纪录保持者”，条件是从走廊入口走到他这里，他手里的数字必须不小于前面所有人手里的数字。这里“前面所有人里的最大值”才是关键，而不只是前面那个人。好节点就是二叉树里的“纪录保持者”。
等价转换一下：好节点等价于“当前节点值 >= 从根到当前节点的路径最大值”。这个转换很关键，因为路径最大值是可以在遍历过程中单调维护的。如果当前节点值大于等于当前路径最大值，它就是好节点；同时，路径最大值更新成当前节点值。如果小于，则路径最大值保持不变，继续往下传。
1.2 根节点、相等值、负值三个隐藏细节
根节点是天然的好节点，因为从根到根自己路径上只有它一个节点，不存在比它更大的值。在代码里我们通常用一个极小值初始化路径最大值，这样根节点的判断自然成立，不必单独写 if。
第二个细节是等号。题目说的是“都不大于当前节点值”，翻译成代码是node->val >= curMax，而不是node->val > curMax。相等的情况必须算好节点。比如 [1, 1] 这棵树，根1是好节点，左孩子1路径上的最大值也是1，1 >= 1成立，所以也是好节点。如果是值相同的长链，所有节点全部是好节点。我见过不少人在这一行上栽跟头，因为示例给的数字大多是严格递增的，等号场景很难被主动想到。
第三个细节是负数。因为节点值范围可以到负数，路径最大值的初始值一定不能设成0。正确做法是用 int 的最小值 INT_MIN，或者干脆用第一个节点值当作初始化值。如果用0初始化，那所有负数节点都会被判定为“路径上存在比它更大的值”，从而漏掉。
这三个细节单个看都很小，但组合起来恰恰决定了提交是“一遍过”还是“反复出错”。
2. 解法一：DFS自顶向下传参，把路径最大值当作一张卡片
2.1 递归函数的状态设计
DFS的解法和我们手动推理的过程完全一致。递归函数需要两个信息：当前走到哪个节点，以及走到这个节点时路径上已经出现的最大值是多少。第二个信息就是上面说的“卡片”。
每次进入一个节点，先把手里的卡片值和当前节点值做比较：
- 如果
node->val >= curMax，当前节点是好节点，答案计数加1，并且把卡片更新为node->val； - 如果
node->val < curMax，当前节点不是好节点，卡片保持原样。
然后这个更新完的卡片分别传给左孩子和右孩子。要注意，传给左孩子和右孩子的卡片是同一个值没错，但它们是两个独立的副本，不是同一个引用。因为左子树路径上的最大值变化不能影响右子树的路径记录。这个细节在写代码时特别容易踩，后面边界部分我会专门说。
递归的终止条件是节点为空，返回0。汇总时把“当前节点是否是好节点”（0或1）加上左子树的好节点数再加上右子树的好节点数，就是整棵树的答案。
2.2 代码实现：纯函数风格与成员变量风格
先给出最常见的纯函数递归写法。C++：
class Solution { public: int goodNodes(TreeNode* root) { return dfs(root, INT_MIN); } int dfs(TreeNode* node, int curMax) { if (!node) return 0; int count = 0; if (node->val >= curMax) { count = 1; curMax = node->val; } return count + dfs(node->left, curMax) + dfs(node->right, curMax); } };Python版本几乎是对应的：
class Solution: def goodNodes(self, root: TreeNode) -> int: def dfs(node: TreeNode, cur_max: int) -> int: if not node: return 0 if node.val >= cur_max: cur_max = node.val return 1 + dfs(node.left, cur_max) + dfs(node.right, cur_max) return dfs(node.left, cur_max) + dfs(node.right, cur_max) return dfs(root, float('-inf'))我个人更推荐这种“返回int的纯函数”写法。它不依赖任何类成员变量，每次递归的状态都通过参数和返回值显式传递，逻辑透明，笔试、面试都好沟通。假如用成员变量 ans 来累加，代码会短一点点：
class Solution { private: int ans = 0; public: int goodNodes(TreeNode* root) { dfs(root, INT_MIN); return ans; } void dfs(TreeNode* node, int curMax) { if (!node) return; if (node->val >= curMax) { ++ans; curMax = node->val; } dfs(node->left, curMax); dfs(node->right, curMax); } };两种写法时间复杂度一样。选哪种主要看个人习惯，但面试时我建议先用纯函数版本，因为它更容易向面试官证明“每个子树的结果是独立计算的”。
2.3 复杂度分析：为什么一定是O(n)
每个节点恰好被访问一次，所以时间是O(n)，n是树节点总数。空间上主要消耗在递归调用栈，递归深度等于树的高度。树完全平衡时高度是O(logn)，树退化成一条链时高度是O(n)。所以最坏空间复杂度O(n)，平均O(logn)。
可能有人会问：既然答案要累加所有好节点数量，有没有可能像“树形DP”那样需要后序遍历？不需要。这道题的判定只依赖从根向下的路径信息，属于“自顶向下的状态传递”，而好节点数量本身又是在递归返回时累加的，因此前序、中序、后序其实都无所谓，只要保证进入节点时能拿到从根到该节点的路径最大值。这也是这类题和经典树形DP的最大区别。
3. 解法二：BFS用显式队列保存路径状态
3.1 为什么要从DFS换到BFS：递归爆栈的现实问题
DFS递归写起来很清爽，但它有一个隐患：当树退化成单支链，递归深度等于节点数。LeetCode上节点数可以到10^5，如果平台给的单支链用例足够深，递归版代码在一些环境下可能直接爆栈。虽然LeetCode的C++栈空间相对宽松，大部分时候不会挂，但这并不是一个可以忽略的风险。
BFS用显式队列替代系统递归栈，从数据结构层面规避了栈溢出问题。它唯一的代价是代码稍微多几行，队列中每个元素要额外带上“路径最大值”这个状态。面试时如果被问到“递归爆栈怎么办”，能马上给出这个版本，会是个很好的加分点。
3.2 队列元素怎么设计：节点和对应该节点的路径最大值
BFS的思路和DFS完全一致：队列里每一个元素代表“到达某个节点时，手上这张路径最大值卡片的状态”。所以我们存的是(node, curMax)的二元组，而不是只存节点。
从队头取出一个元素后，做和DFS一模一样的判断：node->val >= curMax则是好节点，并更新curMax；然后把左孩子、右孩子连同更新后的curMax一起加入队尾。因为每个队列元素只属于一条具体的根到节点的路径，兄弟分支之间的状态天然隔离，不会串。
C++实现：
class Solution { public: int goodNodes(TreeNode* root) { if (!root) return 0; int ans = 0; queue<pair<TreeNode*, int>> q; q.push({root, INT_MIN}); while (!q.empty()) { auto [node, curMax] = q.front(); q.pop(); if (node->val >= curMax) { ++ans; curMax = node->val; } if (node->left) q.push({node->left, curMax}); if (node->right) q.push({node->right, curMax}); } return ans; } };Python：
from collections import deque class Solution: def goodNodes(self, root: TreeNode) -> int: if not root: return 0 ans = 0 q = deque([(root, float('-inf'))]) while q: node, cur_max = q.popleft() if node.val >= cur_max: ans += 1 cur_max = node.val if node.left: q.append((node.left, cur_max)) if node.right: q.append((node.right, cur_max)) return ans注意上面 C++ 里的结构化绑定auto [node, curMax]需要 C++17。如果你在较老的环境里写题，用q.front().first和q.front().second更保险。这个点很小，但能体现你对编译标准是否有意识。
3.3 BFS与DFS的性能对比
时间上，两种方法都是O(n)，实际运行时间差别通常不超过几个百分点。空间上，DFS最坏O(h)，BFS最坏O(w)，h是树高、w是最大层宽。完全二叉树中，最后一层节点数约n/2，所以BFS在空间上可能比DFS更占内存；但单支链时，BFS队列最多只有一个节点，而DFS递归深度是n。不存在一个绝对更优的选择，要根据树的形状判断。
| 维度 | DFS递归 | BFS迭代 |
|---|---|---|
| 时间 | O(n) | O(n) |
| 空间 | O(h)，链表时O(n) | O(w)，最差O(n) |
| 爆栈风险 | 树高过大时有 | 无系统栈风险 |
| 代码量 | 少，逻辑直观 | 略多，需显式维护状态 |
| 适用场景 | 常规刷题、讲解思路 | 极端树高、面试现场换迭代 |
刷题的时候我一般先写DFS，如果面试官追问“能不能不用递归”，再平静地切到BFS版本。这个节奏最自然。
4. “耗时100”复盘：真的有必要抠那几十毫秒吗
4.1 提交耗时100ms是什么概念
我在LeetCode上提交这道题的C++解法时，记录里出现过耗时100ms，而看评论区有些人贴出30ms甚至20ms的成绩，第一反应是“我是不是写慢了”。复盘之后我的结论是：100ms这个数字对这道题来说一点都不算差，甚至大概率是正常波动范围内的成绩。
原因是多方面的。LeetCode的运行时间严重依赖服务器当前负载，同一份代码在不同时间提交，可能从40ms波动到120ms。我看过有人拿完全相同的代码连续提交五次，最大值和最小值能差一倍以上。另外，树的形态对缓存命中率、分支预测也有影响，深链和宽树的遍历模式很不一样。所以，刷题平台的耗时数字只能当参考，不能当作严谨的基准测试。
4.2 从代码层面看真正的优化点
抛开平台波动，这道题代码层面确实有一些可以抠的地方。第一个是变量作用域：如果递归函数里count变量定义在函数体内部，每次递归调用都会在栈上分配和释放，虽然编译器通常能优化掉，但写成直接 return 的形式更干净。上面那个Python版本就体现了这一点。
第二个可优化点是传参方式。C++的 int 参数天然是值传递，开销极小；但如果你把curMax设计成引用int&，不仅没有性能收益，反而会引入兄弟子树状态串扰的严重bug，这个我下一节会细说。
第三个点是数据结构。BFS方案里queue<pair<TreeNode*, int>>每个元素会有一次额外的pair拷贝，数据量大时会有开销。追求极致时可以用 deque 或者自定义小结构体，但对10^5节点来说，这些时间加在一起可能也就几毫秒，属于“理论上存在、实践中无感”的优化。我更愿意把精力放在保证代码不引入额外扫描上。
提示：这道题真正会导致耗时爆炸的写法，是在每个节点上重新扫描一次从根到它的路径。比如先找根到某个节点的路径数组，再判断最大值，总复杂度就退化成O(n^2)或者O(n * 树高)。如果是这种写法，即使小数据能过，大数据也会明显超时。判断自己是否写对，最简单的办法是看复杂度是不是O(n)。
4.3 别被刷题平台的耗时数字带偏
我个人对“耗时100”这类刷题记录的态度是：先确认复杂度，再确认边界情况，最后才轮得到常数优化。LeetCode上的耗时是一个很粗粒度的指标，它受语言版本、编译器优化选项、服务器负载、甚至网络传输的微小抖动影响。与其盯着100ms和80ms的差距，不如把时间花在把思路讲清楚、把边界用例测全上。
如果你真的想验证某个写法是不是更快，别在LeetCode上反复提交，把同样规模的测试数据放到本地，用相同的编译器和优化级别跑十次取中位数，这样才有参考价值。这道题我本地测过，递归版和迭代版在10^5节点规模下基本打平，差距都在噪声范围内。
5. 边界情况与易错点排查：从一次负数用例翻车说起
5.1 错误案例：初始值0导致的负数翻车
我第一次提交时，在递归入口把curMax初始化成了0。当时的想法很朴素：“反正要找最大值，用0当起点很自然。” 结果提交后有一个用例直接错了，输出比预期少。我看了测试数据才知道，树里全是负数节点，初始0把整棵树的路径最大值都抬高了，导致所有负数节点都不满足node->val >= curMax。
这个坑暴露出的本质问题是：路径最大值必须在“真实存在的节点值”和“一个绝对小值”之间做选择。最稳妥的办法就是用 INT_MIN（C++）或float('-inf')（Python）作为初始值，它能保证根节点的判断一定成立，同时不影响任何节点值的比较。如果题目明确节点值都是正数，用0也没问题，但既然范围包含负数，就不要偷懒。
5.2 相等情况：好节点判定中的等号
另一个容易错的是等号。题目说的是“都不大于当前节点值”，也就是说当前节点值大于等于路径所有值时，它就是好节点。考虑一棵完全由1组成的5节点二叉树，按定义，根节点和所有子节点全都满足条件，答案应当是5。
如果写成严格大于，这棵树输出会变成1，直接崩盘。为什么会有人写严格大于？因为很多类似问题问的是“严格大于祖先的最大值”，或者“唯一最大值”这类条件，做多了容易手滑。我的建议是把这道题的判定条件单独抄在草稿纸上：node->val >= curMax，然后旁边写一行注释：等号也计入。
5.3 树形结构带来的空间复杂度陷阱
除了值上的边界，树本身的形状也是重要的边界条件。单节点树只有根，答案必然是1，代码能否正确处理取决于入口处是否传入了初值。空树在题目中通常不会出现，但为了防御性，还是建议判空返回0。
单支链是最考验空间复杂度的用例。假设10^5个节点排成一条线，且值严格递增，那么每个节点都是好节点，答案就是n；但递归深度也是n，如果平台栈空间不够，递归版代码可能直接Runtime Error。遇到这种情况，BFS/显式栈版本就是可靠的兜底方案。我之前在本地用一个很深的单链测试过，递归版在到达某个深度后就直接崩了，换成BFS版稳稳通过。
| 测试用例 | 预期输出 | 关键点 |
|---|---|---|
| root = [3,1,4,3,null,1,5] | 4 | 原题示例 |
| root = [1,1,1,1,1] | 5 | 等号必须成立 |
| root = [-3,-1] | 2 | 初始值不能用0 |
| root = [1] | 1 | 根节点永远是好节点 |
| root = null（若允许） | 0 | 防御性判空 |
| root = [2,null,4,10,8,null,null,4] | 4 | 右斜单链，路径最大值传递 |
6. 进阶扩展：这道题背后的一类“路径状态传递”题型
6.1 改判定条件的变式题
1448最核心的套路是“在遍历过程中携带一个从根到当前节点的状态值”。把状态值从最大值换成其他东西，就能延伸出一系列题目：
- 把判定条件改成“当前节点值大于路径上所有值之和”，就变成路径和条件下的计数问题；
- 改成“当前节点值大于父节点值”，就变成严格递增路径上的计数问题；
- 把统计好节点改成统计每条根到叶子路径上的最小值，状态值换成 min 即可；
- 改成“路径上所有节点值互不相同”，则需要携带一个哈希集合或者更复杂的结构，瞬间从中等难度变成困难。
这些变式的共同点是：路径状态在分支之间是独立的，必须按值传递或在新分支中复制，不能共享。理解了1448，就等于理解了这一大类题的结构。
6.2 面试官常问的延伸问题
面试里这道题通常不会只让写代码。常见追问包括：
- 为什么递归解法是O(n)？能给出空间复杂度吗？
- 如果树深度很大，递归爆栈怎么办？
- 如果节点值类型是 long long，初值怎么设置？
- 如果要求同时输出所有好节点的值，而不是只计数，怎么改？
- 如果允许修改节点的数据结构，你会怎么设计来简化这个统计？
第4个问题尤其值得动手改一遍：在DFS中遇到好节点时，除了计数还 push 到结果数组，最后返回这个数组。改动量很小，但对“状态传递”的理解会更深。
第5题有点开放，我遇到过的最好答案是：在节点结构里加一个字段记录从根到该节点的最大值，一遍前序遍历填好这个字段，第二遍统计。虽然时间复杂度变成O(2n)，但思路很清晰。我还会反问面试官是否可以修改原树供后续复用，来展示你的工程思维。
6.3 如何用这道题做热身训练
如果你想拿这道题做面试热身，我建议的顺序是：
- 先口述题意和好节点判定条件，边说边把“等号算好节点”“根节点自然满足”这些边界点提出来；
- 手写纯函数DFS解法，控制在5分钟以内；
- 主动补一个BFS迭代版，说明是为了应对爆栈；
- 自己在脑子里过一遍负数值、相等值和单支链三个测试用例；
- 最后把扩展问题里的“输出所有好节点值”也改一下。
整套流程走下来十分钟左右，比盲目刷十道同类题有效得多。这类简单树题的价值不在题解本身，而在于把遍历、状态传递、边界控制这些基础功练扎实。你后面刷路径和、最大路径值差、二叉树最近公共祖先等中等题时，都会用到这里面的思维模式。
我个人到现在刷数组和字符串题偶尔还是会马虎，但树的题很少再出边界错误，就是因为当初把1448这一类题抠得很细。LeetCode上显示的那次100ms提交，现在回头看更像是一个提醒：别急着跟评论区比速度，先确认自己真的把每个细节都想透了。能做到这一点，一道简单题的收获不一定比难题少。
