LeetCode 1448Count 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路径上的最大值也是11 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 代码实现纯函数风格与成员变量风格先给出最常见的纯函数递归写法。Cclass 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; queuepairTreeNode*, 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; } };Pythonfrom 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]需要 C17。如果你在较老的环境里写题用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方案里queuepairTreeNode*, 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_MINC或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初始值不能用0root [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提交现在回头看更像是一个提醒别急着跟评论区比速度先确认自己真的把每个细节都想透了。能做到这一点一道简单题的收获不一定比难题少。