先说结论LeetCode 1372也就是不少题单里写的 Lc338-1372是一道非常典型的二叉树中等难度题目考察的是在树上做状态转移的基本功。我第一次用 Java 刷这道题时第一反应是枚举每个起点再逐层往下探索结果代码写得很绕提交后还超时。后来把视角从路径起点切换到每个节点能往哪个方向延伸问题一下子就清晰了。这篇文章我不仅会给出一份可以直接提交的 Java 版完整代码还会把状态定义、转移过程、边界条件都拆开讲透最后结合我自己踩过的坑聊一聊二叉树 Java 代码里最常见的运行时错误到底是怎么来的。这道题在算法面试里属于看着不难、一写就乱的类型适合刚刷完二叉树遍历、准备进阶 DP 的 Java 开发者也适合面试前想快速过一遍树形 DP 思路的同学。1. 先把题目读懂什么是最长交错路径1.1 交错路径的定义拆解题目本身不复杂在一棵二叉树里从任意节点出发每一步选择左孩子或右孩子往下走但要求每一步的方向必须和上一步相反。也就是说如果你上一步走的是左下一步只能是右再下一步又只能是左。整条路径不能出现连续两个相同方向。这就是交错路径的核心约束。很多朋友第一次看题目时容易忽略一个关键点路径的起点不一定是根节点可以从任意节点开始。这个自由度直接决定了我们不能简单套用求树最大深度那种从根出发的模板。举个例子一棵根节点只有左孩子、左孩子又有左孩子的链状树从根出发只能一直往左这并不构成交错路径。但如果从根节点的左孩子出发它也不能继续往左所以长度很短。真正的最长交错路径可能藏在某个子树内部甚至是从某个节点先向右、再向左、再向右这样蜿蜒出去的。1.2 返回长度是边数不是节点数这是这道题最容易踩的坑之一。题目明确说了交错路径的长度定义为访问到的节点数减去 1也就是路径上经过了多少条边。举个例子如果最长交错路径访问了 5 个节点那么返回值是 4不是 5。单个节点没有边长度为 0空树按题意也返回 0。我在 LeetCode 讨论区见过不少题解把返回值写成节点数代码逻辑没问题但例子跑出来始终比预期多 1最后一看是定义没对齐。所以写代码前先把长度的口径固定下来我们维护的每一个状态值都代表从某个起点出发、走特定方向后形成的边数。1.3 暴力枚举为什么不能直接用最直观的暴力思路是枚举每个节点作为起点再分别向左、向右尝试扩展每扩展一步就切换方向直到走不动为止然后记录全局最大值。这个思路理论上没错但复杂度在极端情况下是 O(n^2)。二叉树可以退化成一条链每个节点作为起点都可能往下走一整条路径。如果树有 n 个节点最坏要处理的路径数量接近 n^2在 LeetCode 的测评数据下很容易超时。而且代码里要写两套递归一套枚举起点、一套扩展路径很容易把方向状态搞混。所以这道题的正确打开方式不是枚举起点而是从终点倒推状态用一次遍历把所有节点的状态都算出来。这也是树形 DP 最常见的套路。2. 核心思路从路径起点转向方向状态2.1 关键观察走到某个节点后下一步方向已经被锁死假设你正沿着一条合法交错路径走现在站在节点 X 上。请问你下一步能往哪走答案完全取决于你上一步是从哪个方向过来的。如果你上一步是从父节点向左走到达 X那么下一步必须向右如果你上一步是从父节点向右走到达 X那么下一步必须向左。换句话说一个节点能不能继续延伸不取决于它自身而取决于进入它的方向。这个观察非常重要它意味着我们不需要知道整条路径的起点在哪只需要知道当前节点作为路径端点时下一步期望的方向是什么。基于这个观察我们不需要枚举起点只需要对每个节点记录两种状态如果从它出发第一步向左能延伸多长如果从它出发第一步向右能延伸多长。这两类状态可以通过子树的信息递推出来。2.2 定义两个状态向左出发与向右出发对于任意节点 u我们定义两个值leftLen[u]从 u 出发第一步向左走能够形成的最长交错路径长度按边数计。rightLen[u]从 u 出发第一步向右走能够形成的最长交错路径长度。注意这里的第一步方向决定了整条路径后续的方向序列。如果第一步向左那么第二步必须向右第三步必须向左……所以整个路径的方向是被起点第一步的方向唯一确定的。这比直接定义从 u 出发的最长交错路径要精确得多因为从 u 出发可能有两种不同的方向选择合在一起反而无法递推。2.3 状态转移方程怎么推先看 leftLen[u]。要形成第一步向左的路径u 必须先走到左孩子 left。这一步贡献了 1 条边。到达 left 之后后续的路径方向必须与向左相反也就是从 left 出发必须第一步向右。所以leftLen[u] 1 rightLen[left]前提是 left 存在如果 u 没有左孩子那么 leftLen[u] 0因为无路可走。同理rightLen[u] 1 leftLen[right]前提是 right 存在否则为 0。这个递推过程很自然地依赖于子节点的状态所以我们必须先计算左右子树的结果再用它们拼出当前节点的状态。这正是后序遍历的应用场景。2.4 拿一棵小树实际推一遍为了确认公式没问题我拿一棵具体的小树手动模拟。假设树的结构是根节点 1左孩子 2节点 2 有一个右孩子 3节点 3 有一个左孩子 4。节点 4 是叶子leftLen[4] 0rightLen[4] 0。节点 3 有左孩子 4leftLen[3] 1 rightLen[4] 1没有右孩子rightLen[3] 0。节点 2 没有左孩子leftLen[2] 0有右孩子 3rightLen[2] 1 leftLen[3] 1 1 2。节点 1 有左孩子 2leftLen[1] 1 rightLen[2] 1 2 3没有右孩子rightLen[1] 0。最长的交错路径是 1 - 2 - 3 - 4方向依次为左、右、左长度为 3和手工计算完全一致。这个例子也说明了一个容易忽略的点路径可以穿过左子树再绕到右子树但状态转移天然地把这种绕行算进去了因为我们用的是从孙节点出发的反向状态来拼接的。3. Java 完整实现与逐行解读3.1 后序遍历数组返回的经典写法下面的代码是 LeetCode 1372 的 Java 解法中最稳的一版。我使用一个递归函数返回长度为 2 的数组分别代表当前节点第一步向左和第一步向右的最长交错长度同时用全局变量维护答案。class Solution { private int ans 0; public int longestZigZag(TreeNode root) { if (root null) { return 0; } dfs(root); return ans; } // res[0]从 node 出发第一步向左的最长交错路径长度 // res[1]从 node 出发第一步向右的最长交错路径长度 private int[] dfs(TreeNode node) { int[] res new int[2]; if (node.left ! null) { int[] leftChild dfs(node.left); res[0] 1 leftChild[1]; } if (node.right ! null) { int[] rightChild dfs(node.right); res[1] 1 rightChild[0]; } ans Math.max(ans, Math.max(res[0], res[1])); return res; } }这段代码量很小但每一行都有它的道理。我们逐个拆开来看。3.2 为什么用返回两个值而不是传方向参数有人在写这道题时会选择另一种写法递归函数携带一个方向参数和一个累计长度每次尝试延续或重新开始。这种写法初看更符合直觉但存在两个问题一是每个节点可能被重复访问多次极端链状树会退化成近似 O(n^2) 的复杂度二是延续和重置两个分支写在一起非常容易漏掉其中一种情况。返回数组的后序遍历没有这两个问题。每个节点只会被访问一次左右子树的结果算完后用常数时间拼出当前节点的状态整体复杂度就是 O(n)。这也是我在实际做题时更推荐的方案面试时跟面试官解释起来也更流畅先用子节点的反方向状态加上当前这条边构成当前方向的状态最后在所有状态里取最大值。3.3 关键边界条件梳理空树直接返回 0。只有一个节点两个状态都是 0ans 保持 0返回 0。节点只有左孩子没有右孩子res[0] 1 leftChild[1]如果左孩子是叶子leftChild[1] 0那么 res[0] 1表示节点到左孩子这一条边构成一条长度为 1 的交错路径。答案更新放在返回之前因为返回数组只代表当前节点的状态而最长交错路径可能出现在任意子树内部所以每个节点的状态都要与全局 ans 比较一次。我第一次写的时候把 Math.max(ans, ...) 放在了 dfs 调用之前结果子树的答案没统计进去某些用例会少算。后来把更新操作移到状态计算完成之后问题就消失了。3.4 复杂度分析时间复杂度O(n)每个节点恰好被 dfs 访问一次。 空间复杂度O(h)h 是二叉树的高度。递归调用栈占据额外空间最坏情况下树退化成链h 等于 n但一般测评数据不会这么极端。4. Java 二叉树常踩的坑与排查思路每次看到有同学在评论区问写二叉树程序时为什么总是报运行时错误我都能猜到大概是哪几类问题。这里结合这道题的实际场景把最典型的坑一次性说清楚。4.1 NullPointerException九成二叉树报错都是它二叉树代码里空指针异常是最常见的运行时错误。典型场景是递归函数里直接访问了 node.left但当前节点可能是 null或者判断了 node.left ! null却忘了判断 node.left.left 在下一层递归是否安全。就拿上面的题来说如果我在写 dfs 时直接写node.left.val而不检查 node.left 是否为空遇到叶子节点立刻就会抛 NullPointerException。正确的写法是先判空再访问或者把空判断放在递归函数入口。还有一种隐蔽的写法错误把空判断写反了比如if (node.left null) { res[0] 1 dfs(node.left)[1]; // 这里逻辑是反的null 节点根本没有状态 }这种代码不报异常才怪。排查思路很简单看到异常栈指向某个 .java 文件的某一行先看那一行的对象引用是不是可能为 null再往回追它有没有被赋值、有没有判空。4.2 递归基准条件写错导致无限递归比空指针更隐蔽的是逻辑上没错、但递归没有正确出口。常见于基准条件应该判断当前节点为 null 就返回结果写成了当前节点的左孩子为 null 就返回在某些形态的树上会漏掉分支甚至无限递归。排查这种问题时我习惯用一个极端的例子测试只有一个节点的树、只有左孩子的链状树、完全二叉树、随机二叉树。如果某个用例卡死或者结果不对基本就能锁定是基准条件的问题。4.3 返回值口径不一致明明逻辑对答案差 1这道题还有一个经典场景代码整体没报错但提交后总有一两个用例不对而且不是超时就是答案比预期大 1 或小 1。这时候十有八九是长度定义没有统一。我在 1.2 里专门强调过本题返回的是边数而不是节点数。如果在状态转移里把起点本身也算成了长度 1那么所有答案都会偏大。检查方法非常简单手动模拟一个 3 个节点的交错路径预期结果应该是 2如果代码输出 3说明你把节点数当成长度了。4.4 树形 DP 面试自查清单结合这道题我把二叉树类的常见面试考点整理成一张速查表方便你在面 Java 岗之前快速过一遍常见错误典型现象排查思路空指针访问了 null 节点的属性先看异常栈行号检查引用是否为 null递归无出口程序栈溢出或卡死检查基准条件是否覆盖所有空节点情况返回值口径错误答案总是差 1对齐边数/节点数的题目定义方向状态更新遗漏答案偏小确认每个节点的所有方向状态都参与比较重复递归导致超时大数据量级用例超时改用后序遍历避免每个节点被反复访问这张表里的最后一条对应的是很多人在面试现场写代码时会犯的错为了省事给每个节点都重新递归一遍子树。看起来代码更短复杂度却飙到 O(n^2)。面试官让你分析复杂度时一下就露馅了。在这道题里正确的树形 DP 思路是自底向上、一次遍历、状态合并。这个模式不仅仅适用于最长交错路径很多二叉树类的动态规划题比如打家劫舍 III、二叉树中的最大路径和基本都是同一个套路递归返回一个或多个状态值父节点根据子节点的状态做组合全局变量记录答案。我个人的体会是刷树形 DP 不要急着看题解先拿纸笔画一棵小树手动模拟几个节点的状态转移把公式写出来再动手敲代码。这样即使面试时遇到变体题也能快速定位出状态定义和转移方向。最后再多说一句代码提交前跑一遍单节点树和链状树这两个极端用例能帮你躲开至少一半的边界错误。