博主经验也不算多但LeetCode刷了三百来道Java版二叉树这块踩坑不少。这次拿Lc336-1448这道“统计二叉树中好节点的数目”来聊聊题目本身不复杂但背后的DFS思路、Java实现细节还有面试时怎么答得让面试官眼前一亮都有讲究。如果你正在准备Java后端面试或者刷题卡在二叉树这一类这篇应该能帮你省点时间。很多人刷题只关注“AC了没有”但我要说的是这道题值得慢下来做一遍。它考察的不只是“能不能写出递归”而是你对DFS遍历过程的理解深度——你在递归过程中究竟传递了什么信息这决定了你能不能在 O(n) 时间内数完所有好节点。面试官问这类题想看的也是你拆解问题的思路不是背答案。1. 题目理解与解题思路拆解1.1 先搞懂“好节点”的定义题目给一棵二叉树每个节点上有一个整数值。所谓“好节点”指的是从根节点到该节点的路径上这个节点的值大于等于路径上所有其他节点的值。换句话说它是这条路径上的“历史最大值”。我第一次读题的时候差点理解歪了以为是和所有祖先节点比较后来发现“路径上的最大值”这个表述更准确。根节点天然是好节点因为从根到根这条路径上只有它自己没有比它更大的也没有比它更小的。举个小例子3 / \ 1 4 / / \ 3 1 5根节点3是好节点。左子树节点1路径是3-11小于3不是好节点。节点3左子树的左孩子路径是3-1-3最大值是3当前值也是3是好节点。右子树节点4路径3-44大于3是好节点。节点1右子树的左孩子路径3-4-1最大值是41小于4不是好节点。节点5路径3-4-5最大值是5是好节点。所以总数是4个。这个例子我建议你自己在纸上画一遍理解“路径最大值”这个变量在递归过程中是怎么变化的后面写代码就顺了。1.2 为什么这道题用DFS而不是BFS拿到二叉树题目第一反应可能是层次遍历BFS但这道题用BFS做会很别扭。原因是好节点的判定依赖“从根到当前节点的整条路径”而BFS是逐层扫描的你需要在队列里额外维护每个节点对应的路径最大值逻辑上绕了一圈。DFS深度优先搜索天然契合这种“路径关联”的判定。递归向下走的时候路径是自然串联的你只需要在每一层把当前的最大值传下去就行。前序遍历、中序遍历、后序遍历都可以做但最直观的是前序遍历——先处理当前节点再递归左右子树和“从根往下判断”的顺序一致。用生活类比来解释想象你在山里爬一条路线每到一个观景台节点你比较一下当前海拔和之前到达的最高海拔如果当前更高就记一个“新高度记录”。你只需要记住一个“到目前为止的最高海拔”这个变量走到哪个观景台都比对一下。DFS就是这个“一路走到底再回头”的过程。1.3 核心思想把“历史最大值”作为递归参数这道题的关键就一句话递归时携带一个参数记录从根到当前节点的路径最大值。每次递归进入一个节点做三件事如果当前节点值为 null直接返回 0。比较当前节点值 cur 和传入的路径最大值 maxSoFar如果 cur maxSoFar说明当前节点是好节点计数加一并更新 maxSoFar cur。递归处理左右子树把更新后的 maxSoFar 传下去累加两者的结果。这个思路非常简单但你要理解为什么参数传递能生效因为每一次递归调用都是一个独立的栈帧参数在调用时被复制。左子树走了更新后的最大值右子树拿到的是同一个更新后的最大值互不干扰。这也是DFS回溯的天然优势。2. Java实现细节与代码实战2.1 先定义二叉树节点类LeetCode 默认给的节点类是常规的二叉树节点定义Java 版长这样public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode() {} TreeNode(int val) { this.val val; } TreeNode(int val, TreeNode left, TreeNode right) { this.val val; this.left left; this.right right; } }这个定义在日常刷题中太常见了我建议你直接背下来。它本质是一个“自引用结构”每个节点持有左右子节点的引用null 就代表没有子树。写代码的时候注意别把 left 和 right 搞反我见过不少初学者构造测试用例时把左右子树传反了导致结果对不上。2.2 主方法设计入口方法 递归辅助方法LeetCode 要求实现的是一个方法通常长这样public int goodNodes(TreeNode root) { return dfs(root, Integer.MIN_VALUE); }递归辅助方法单独抽出来携带 maxSoFar 参数private int dfs(TreeNode node, int maxSoFar) { if (node null) { return 0; } int count 0; if (node.val maxSoFar) { count 1; maxSoFar node.val; } count dfs(node.left, maxSoFar); count dfs(node.right, maxSoFar); return count; }入口方法用Integer.MIN_VALUE作为初始最大值这个设计很巧妙。因为根节点无论如何都满足root.val Integer.MIN_VALUE除非根节点值也是极小值但节点值范围在 -10^4 到 10^4 之间不会出现这种情况所以根节点自动计为好节点。这就省掉了单独判断根节点的代码逻辑非常干净。我把主方法和递归方法拆开的理由是入口方法保持简洁递归方法只管“当前节点 左右子树”的累加。这样代码可读性高面试时也好解释。有些人喜欢把初始逻辑直接写在递归方法里加个 if 判断也能跑通但多少有点绕。2.3 完整代码与逐步执行追踪放出可以直接跑的完整代码class Solution { public int goodNodes(TreeNode root) { return dfs(root, Integer.MIN_VALUE); } private int dfs(TreeNode node, int maxSoFar) { if (node null) { return 0; } int count 0; if (node.val maxSoFar) { count 1; maxSoFar node.val; } count dfs(node.left, maxSoFar); count dfs(node.right, maxSoFar); return count; } }我拿刚才那颗树手动追踪一遍dfs(3, -∞) → 3 -∞count1max3 dfs(1, 3) → 1 3count0max保持3 dfs(3, 3) → 3 3count1max3 → 总数 1 dfs(4, 3) → 4 3count1max4 dfs(1, 4) → 1 4count0 dfs(5, 4) → 5 4count1max5 → 总数 2 最终 1 1 2 4注意一个细节节点值等于路径最大值时也算好节点。LeetCode 原题的表述是“大于等于”别记成“大于”。我第一次做的时候用了大于结果一直差一个数排查了半天才发现是边界条件看漏了。这个点面试时也经常被拿来考察审题是否仔细。2.4 为什么初始值选 Integer.MIN_VALUE 而不是别的有人可能会问初始最大值能不能用root.val逻辑上也可以但需要先判断根节点是否为空然后从根节点开始递归。代码会变成这样public int goodNodes(TreeNode root) { if (root null) { return 0; } return 1 dfs(root.left, root.val) dfs(root.right, root.val); }这样也能过但入口方法里有了一个1 的固定计数递归方法里就不用再判断根节点了。两段代码都能跑但从统一性和简洁性来说Integer.MIN_VALUE的版本更干净——你不需要单独处理根节点所有节点一律走同一套逻辑。我实际面试时曾经写过第二个版本面试官追问“为什么递归不用传根节点的值作为初始值”我说“好的那我改成用 Integer.MIN_VALUE 来统一逻辑”面试官点头表示认可。这种小细节体现了你对代码简洁性的追求。3. 复杂度分析与面试进阶思路3.1 时间与空间复杂度O(n) 时间、O(h) 空间时间复杂度很容易分析每个节点恰好被访问一次做常数次操作。树的节点数为 n总时间就是 O(n)。这个复杂度已经是最优了因为无论如何你都得遍历整棵树才能判断每个节点。空间复杂度稍微需要多说一句。递归调用会占用系统栈空间栈的深度等于树的高度 h所以空间复杂度是 O(h)。这里的 h 是树的高度最坏情况下比如一棵链状的树退化成单链表h 等于 n空间复杂度退化为 O(n)。最好情况下平衡二叉树h 等于 log₂(n)空间复杂度就是 O(log n)。面试时我建议主动说出这一层分析时间 O(n)空间 O(h)并说明 h 在失衡树和平衡树下的差异。这比干巴巴念出“O(n)”要有说服力得多。面试官如果追问“能不能做到 O(1) 空间”你可以回答如果只考虑递归做不到因为系统栈本身需要 O(h) 空间如果用 Morris 遍历可以做到 O(1) 空间但会修改树的结构通常不推荐。3.2 出口参数为什么用 int 而不是全局变量有些解法会用全局变量来计数每遇到一个好节点就加一。比如class Solution { int ans 0; public int goodNodes(TreeNode root) { dfs(root, Integer.MIN_VALUE); return ans; } }这种写法也能过但我个人不推荐。原因有几个全局变量在并发环境下有线程安全问题虽然刷题时不会遇到但会养成坏习惯。全局变量让函数的“输入-输出”关系变得隐式可读性差。递归过程中如果出现异常或提前返回全局变量的状态可能没被正确重置排查起来麻烦。函数式返回结果的好处是每个递归调用都是自包含的返回值清晰地表达了“这棵子树里有多少个好节点”测试时也更容易单独调用某个子树来验证。面试时你甚至可以补一句“我用返回值累加这样每次递归的职责更单一也避免使用可变的全局状态。”这句话在面试官听来比你多刷一百道题都有用。3.3 从前序遍历视角重新理解这道题这道题本质上就是前序遍历的变体。标准的前序遍历是“根 - 左 - 右”每到一个节点只是访问它的值。而“统计好节点”是在前序遍历的基础上多维护了一个“路径最大值”的变量。如果你对前序遍历的递归模板很熟会发现这道题的框架和它几乎一样// 标准前序遍历 void preorder(TreeNode node) { if (node null) return; // 访问node preorder(node.left); preorder(node.right); }差异就在于“访问”这一步多了判断和更新最大值。所以如果你刷题时能把一道新题映射到自己熟悉的模板上解题速度会快很多。这也是为什么很多人强调“二叉树的遍历是基础中的基础”你掌握了遍历就等于掌握了这一系列题目的骨架。3.4 类似的二叉树衍生题有哪些这类“在遍历路径上维护一个状态”的题目其实有一个家族我列几个你刷完这道题可以顺带走一遍题目维护的路径状态核心差异二叉树的最大深度层数归并时取 max而不是累加计数路径总和剩余 targetSum每次递归减去当前节点值二叉树的所有路径路径字符串回溯时需要移除已访问节点二叉树中第二小的节点当前最小值通常需要两层递归统计好节点数目本题路径最大值判断当前值 历史最大值刷这些题最好的方式不是挨个刷而是刷一道总结一道找到它们之间的“变与不变”。不变的是递归遍历的骨架变的是“维护什么状态、在哪里判断、返回值如何累加”。4. 实操中的常见问题与排查技巧4.1 写二叉树递归时最常见的运行时错误网上常有人问“写二叉树程序时为什么总是报运行时错误”我总结下来90% 的情况是下面几个原因。第一没有判空。递归方法的第一步如果不是判 null一旦访问到空节点就会抛 NullPointerException。这个错误在 LeetCode 上会直接报java.lang.NullPointerException。像这道题dfs 方法进来第一行永远要写if (node null) return 0养成肌肉记忆。第二树的构造测试用例写错了。很多人自己写 main 方法测的时候把左右子树挂反了或者把子节点挂到不存在的父节点上运行时报错甚至死循环。我建议自己构造测试树时用一张纸先画出树形结构再按结构逐层构造避免凭空手写。第三递归出口不合理导致无限递归。在二叉树题目里无限递归通常意味着你递归调用时没有向 base case 靠近比如漏掉了 left 或 right 的判空或者传参时把子节点传成了当前节点。你可以在递归方法入口打一行日志打印 node.val观察调用顺序是否符合预期。4.2 本地运行测试树的搭建方法LeetCode 上刷题时输入是层序遍历的数组表示但本地 IDE 调试时需要自己构建 TreeNode。我分享一个常用的快速构造方法public class Main { public static void main(String[] args) { // 构造一棵树3 / \ 1 4 / / \ 3 1 5 TreeNode node3 new TreeNode(3); TreeNode node1_left new TreeNode(1); TreeNode node4 new TreeNode(4); TreeNode node3_left new TreeNode(3); TreeNode node1_right new TreeNode(1); TreeNode node5 new TreeNode(5); node3.left node1_left; node3.right node4; node1_left.left node3_left; node4.left node1_right; node4.right node5; Solution sol new Solution(); System.out.println(sol.goodNodes(node3)); // 期望输出 4 } }这种构造方式比较笨但很直观。如果你经常做二叉树题我建议写一个小工具方法支持从层序数组构建二叉树public static TreeNode buildTree(Integer[] arr) { if (arr null || arr.length 0) return null; QueueTreeNode queue new LinkedList(); TreeNode root new TreeNode(arr[0]); queue.offer(root); int i 1; while (i arr.length) { TreeNode cur queue.poll(); if (arr[i] ! null) { cur.left new TreeNode(arr[i]); queue.offer(cur.left); } i; if (i arr.length arr[i] ! null) { cur.right new TreeNode(arr[i]); queue.offer(cur.right); } i; } return root; }注意数组里的 null 代表空节点这个工具方法我用了很久省了非常多手工构造的时间。有需要的可以直接复制。4.3 递归爆栈问题与极端情况如果树的高度很大比如 10000 层递归会栈溢出。Java 默认虚拟机栈深度大概在几千到一万层左右具体取决于 JVM 配置和系统栈大小遇到极端退化树可能StackOverflowError。面试中如果被问到这种极端情况你可以说递归解法适合常规树高如果树的形态极端可以把 DFS 改成显式栈的迭代写法。下面给一个迭代版本的参考public int goodNodes(TreeNode root) { if (root null) return 0; int count 0; DequeObject[] stack new ArrayDeque(); stack.push(new Object[]{root, Integer.MIN_VALUE}); while (!stack.isEmpty()) { Object[] item stack.pop(); TreeNode node (TreeNode) item[0]; int maxSoFar (int) item[1]; if (node.val maxSoFar) { count; maxSoFar node.val; } if (node.right ! null) { stack.push(new Object[]{node.right, maxSoFar}); } if (node.left ! null) { stack.push(new Object[]{node.left, maxSoFar}); } } return count; }迭代版本的好处是显式控制栈不依赖系统栈理论上可以处理任意深度的树只要堆内存足够。坏处是代码稍微长一点而且 Object[] 数组的写法不太优雅。如果你对性能有洁癖可以定义一个小内部类来存放节点和最大值。4.4 排查思路结果不对时如何快速定位如果跑出来的结果和预期不一致我建议按这个顺序排查先检查比较符号。是还是这直接影响相等值节点的判断。再用一棵只有根节点的树测试看输出是不是 1。这能排查初始值和边界条件。再用一条链状树测试比如 1 - 2 - 3看输出是不是 3。这能排查递归路径是否正确。最后再用标准用例测试逐行打印递归进入节点的顺序和手工推演对照。我在本地调试时会在 dfs 方法里加临时日志System.out.println(进入节点: node.val , maxSoFar maxSoFar);观察每次进入节点时 maxSoFar 的变化是否符合逻辑。打完日志删除即可但不建议在生产代码里留。5. 这道题在Java面试中的问法5.1 面试官可能抛出的追问这道题在 LeetCode 上是 Medium 难度但作为面试题面试官不会让你写完就结束通常会有几个追问“为什么根节点一定是好节点”——因为初始值是 Integer.MIN_VALUE任何整数都大于等于它。“如果节点值有负数怎么办”——Integer.MIN_VALUE 初始值依然有效。“如果节点值全是负数呢”——同样有效因为负数 Integer.MIN_VALUE恒成立。“递归和迭代版本你更喜欢哪个为什么”——递归更简洁直观迭代更可控但代码更长。这些追问的目的不是考你背诵而是看你能不能从原理上解释自己的代码。所以刷题时别只看题解要多问自己几个“为什么”。5.2 怎么向面试官表达你的思路面试时表达这道题我建议用这样的逻辑链条先说明这是一道二叉树路径题有个信息需要在路径上传递。这个信息就是历史最大值初始化为最小值。用 DFS 遍历每到一个节点比较当前值与历史最大值。如果满足条件就计数并更新历史最大值。递归左右子树返回左右子树结果之和。这个顺序其实就是你思考问题的自然顺序说清楚这五步面试官已经能确认你理解到位了不需要背术语。千万不要一上来就背代码尤其是“我用了一个 dfs 函数”这种没头没尾的表现面试官很难判断你是不是真的懂了。5.3 写在简历项目里的正确姿势如果你做过刷题笔记或者算法总结项目这道题可以写成一个小的“二叉树路径问题模板”案例。不要直接写“我刷了 LeetCode 1448”而是写“我总结了一套二叉树路径类问题的递归模板覆盖好节点计数、路径总和、最大深度等场景并对比了递归与迭代实现的性能差异”。面试官看到这种描述会觉得你不只是刷题而是有总结归纳的能力。这也是中级工程师和初级工程师的重要区别之一。顺便说一句Java 后端面试中二叉树题目出现频率相当高因为二叉树递归是理解系统栈、函数调用开销、分支递归逻辑的最好载体面试官爱问是有道理的。5.4 延伸从这道题理解递归的本质很多初学者觉得递归难其实递归就两个核心点递推关系 终止条件。这道题的递推关系是dfs(node, max) 当前节点贡献 dfs(left, 更新后的max) dfs(right, 更新后的max)终止条件是node null。只要你把这两个点想清楚递归代码自然就写出来了根本不用背。而且我可以告诉你一个判断递归写法好不好的标准看得懂。如果一段递归代码你需要读三遍才明白说明写复杂了可以尝试拆成辅助方法或者换个参数设计。6. 补充说明与注意事项6.1 关于 LeetCode 题号的说明标题里写的“Lc336-1448”我理解是某份题单里编号 336对应 LeetCode 第 1448 题。如果你做题时发现题号对不上别慌以题目名称为准。LeetCode 上有时候会出现一个问题多个变体或者题号更新导致顺序变化。我的建议是碰到这种题直接搜题目名字“统计二叉树中好节点的数目”或者英文“Count Good Nodes in Binary Tree”比记题号更稳妥。毕竟刷题刷多了你也不可能记住每一题的编号记住思想和模板才是根本。6.2 Java 版本的选择我在本地用 Java 17 跑代码Java 8 也完全兼容因为这道题只用了基础语法没有用到任何高版本特性。如果你在 LeetCode 上提交默认的 Java 编译器版本也支持这段代码。唯一要注意的是如果你的本地环境是 17 但编译时报“源发行版 17 需要目标发行版 17”的警告那是 IDE 里 Project Structure 的 Java 版本没配置好和代码本身无关。把编译器级别调到一致即可。这个问题在面试机试时不太会遇到但本地练习时很常见这里提一句。6.3 配合其他二叉树热词扩展学习热搜词里出现了很多“二叉树的深度”“二叉树的遍历”“完全二叉树和满二叉树”“搜索二叉树”“线索二叉树”这里我帮你梳理一下它们和本题的关系二叉树的深度DFS 递归的经典应用和本题共用同一套递归框架。二叉树的遍历前序、中序、后序、层序是二叉树题的骨架。完全二叉树和满二叉树一种二叉树形态面试常考性质公式。搜索二叉树节点值有序排列常用中序遍历判断合法性。线索二叉树通过空指针建立线索实现非递归遍历进阶内容。我的建议是把“遍历”吃透再逐步扩展到“深度”“路径”“计数”这些变体。不要平均用力更不要一上来就啃线索二叉树这种进阶内容。像本题这样中等难度的路径计数题是性价比很高的练习对象既能扎实基础又能在面试中直接展示思路。6.4 最终经验心得我遇到的大部分 Java 面试者二叉树的题目往往卡在两个点上一是递归的终止条件写错二是状态参数没有想清楚。这道题恰好能同时锻炼这两个点。如果你把这道题独立做出来了而且能把自己写的每个细节都解释清楚那面试中遇到大部分二叉树路径类问题你都有了稳定的思路框架。我个人建议刷题时不要只追求“AC 了就下一题”抽出时间把代码里每个变量为什么存在、每个判断为什么这么写讲清楚收益会远超预期。我自己做这道题时就是从“背模板”到“理解路径最大值为什么能作为参数传递”这个转变之后二叉树系列的题目正确率才明显上来的。
