1. 题目到底在考什么为什么“交错路径”值得单独写一篇如果你刷 LeetCode 刷到 1372 题也就是“二叉树中的最长交错路径”你会发现它不像普通的层序遍历、前中后序遍历那样有模板可以套。我第一次看到这题时也愣了一会儿什么叫交错怎么在树上定义一条路径的方向最长又是什么意思把这三个问题想明白这道题其实就是一个非常典型的树形动态规划问题而且它的状态设计思路能直接迁移到好几道二叉树的进阶题上。先解释一下标题里“Lc338-1372”这个编号。1372 是 LeetCode 官方题号前面那串 Lc338 是我自己维护刷题笔记时的一个索引用来给“树形 DP 与路径问题”这一组题目归档。所以整个标题代表着这是 2026 年刷题记录里编号 338 的一条树形 DP 题解对应 LeetCode 1372使用 Java 实现。回到题目本身。题目说的“交错路径”指从树中任意一个节点出发每走一步只能选择左子节点或右子节点并且方向必须左右交替。先向左走一步下一步就必须向右再下一步又必须向左这样一直下去。路径中的每一步都是往下走的不能回头走父节点。要求返回所有可能的交错路径中经过边数最多的那条路径的长度。这题适合什么人来看如果你是准备 Java 开发岗面试的候选人这题几乎是一个绕不开的树形递归题目如果你刚把二叉树的遍历基础学完想找一道能串起“递归顺序、状态定义、边界处理”的题来练手它也再合适不过。下面我把从读完题到写出最终代码的完整过程拆开讲包括我踩过的坑、写错过的状态以及面试时被追问过的问题。2. 破题思路从“暴力枚举起点”到“左右状态互换”2.1 如果枚举所有起点会怎样最直观的想法是把每个节点都当作交错路径的起点从它开始尝试先向左走一步、再向右走一步……记录能走出的最长长度。这听起来很自然因为路径只能向下走所以最长交错路径一定有一个最高点也就是起点从起点开始一路往子节点方向延伸。那么只要枚举所有起点再对每个起点做一次深度优先搜索就能把所有合法路径都找到。以这棵简单到只剩一条链的树为例1 / 2 / 3从节点 1 出发第一步只能向左到节点 2第二步如果继续向左走到节点 3方向就是“左、左”这两步方向相同不满足交错条件所以从 1 出发的最长交错路径长度是 1也就是 1 到 2 这一条边。从节点 2 出发也只能得到长度 1。整棵树的最长交错路径长度就是 1。这种暴力方法的问题在于复杂度。假设一棵树退化成一条链每个节点只有一个方向可走无论从哪个起点出发都只能得到长度为 1 的答案但为了这个结果你要对 n 个节点各做一次遍历时间复杂度会退化到 O(n²)。一旦树的节点数量来到十几万级别这个方案基本就是超时预定。更关键的是我在暴力解法里会发现一个现象不同起点之间大量计算是重复的。从根节点出发的路径会“经过”从根到某个叶子之间的很多子路径从中间某个节点出发的路径又会把同一个子节点的方向信息再算一遍。有重叠子问题就该想到用动态规划或者记忆化搜索优化。2.2 把状态定义成“第一步方向”重叠子问题的存在意味着我们不需要真的枚举每个起点再重新走一遍而是可以让每个节点只算一次把它的“状态”存下来供父节点使用。这里最核心的一步是把状态定义清楚。我最后采用的是两个状态left[u]以节点 u 为起点第一步走左孩子并且之后每一步都满足交错条件最多能走出的边数。right[u]以节点 u 为起点第一步走右孩子并且之后每一步都满足交错条件最多能走出的边数。注意这两个状态只描述“从当前节点出发、下一步往哪个方向”的最长交错路径长度。它不是“从祖先一路走下来的路径长度”而是完全以当前节点作为起点的信息。这样做的好处是每个节点只需要把自己的两个值返回给父节点父节点就能组合出新的答案。因为路径只能从父节点走向子节点left[u] 这一定义里第一步走了左孩子后下一步必须向右走。所以 left[u] 能不能继续延伸完全取决于左孩子的 right 状态同理right[u] 取决于右孩子的 left 状态。这种“左看右、右看左”的互换关系就是整道题递推式的灵魂。2.3 递推公式怎么落笔现在把上面的关系写成递推式。假设当前节点是 u它的左孩子是 L右孩子是 R如果左孩子 L 存在那么 left[u] 1 right[L]。因为第一步 u 走到了 L这条边算 1接下来从 L 出发必须第一步向右走能走多远就是 right[L]如果左孩子不存在路径根本没法开始left[u] 0。如果右孩子 R 存在那么 right[u] 1 left[R]。因为第一步 u 走到了 R这条边算 1接下来从 R 出发必须第一步向左走能走多远就是 left[R]如果右孩子不存在right[u] 0。整个树的最长交错路径答案就是所有节点上的 left[u] 和 right[u] 取最大值。因为任何一条合法交错路径都会有一个起点而起点一定位于某一个节点上这个节点的 left 或 right 状态正好刻画了以它为起点、第一步往某个方向走的完整路径长度。因此全局最大一定藏在某个状态里。是不是一下子清晰了很多再配合几个具体的例子验证这个递推式其实非常稳定。下面我放一棵稍微复杂一点的树手动推一遍确保没有理解偏差。1 / \ 2 3 / \ \ 4 5 8 / \ / 6 7 9先看叶子节点 4、6、7、9它们没有子节点所以 left 和 right 都为 0。节点 5 有左孩子 6 和右孩子 7left[5] 1 right[6] 1 0 1right[5] 1 left[7] 1 0 1。节点 2 有左孩子 4 和右孩子 5left[2] 1 right[4] 1right[2] 1 left[5] 1 1 2。意思是从节点 2 出发先向右走到 5再从 5 向左走到 6这样的路径算出来是 2 条边也就是 2 - 5 - 6。继续看节点 8它只有左孩子 9left[8] 1 right[9] 1right[8] 0。节点 3 只有右孩子 8left[3] 0right[3] 1 left[8] 1 1 2也就是 3 - 8 - 9。最后看根节点 1left[1] 1 right[2] 1 2 3对应路径 1 - 2 - 5 - 6right[1] 1 left[3] 1 0 1。所以最终最大值是 3。这里要特别说明一个容易走偏的念头有些人一开始会把状态定义成“从左孩子下来还是从右孩子下来”也就是关心父节点到当前节点的方向。这种思路也能写但递推关系会绕很多。相比之下“以当前节点为起点下一步的方向”这个定义最贴近交错路径的原始含义写代码的时候也不容易想岔。2.4 为什么这种方式不会漏解可能有人会问最长交错路径不一定从根节点开始也可能从某个子树中间的节点开始啊比如路径 5 - 6起点是 5这一步确实在整棵树的左子树里没有经过根节点。为什么我们只要算每个节点的 left/right再取全局最大就不会漏掉这种情况关键就在“每个节点都要算一次”这件事上。路径 5 - 6 的起点是 5而 left[5] 和 right[5] 在递归时一定会被算出来。只要这个起点存在于树中它对应的 left 或 right 状态就会进入全局最大值的比较范围。所以不是“只算根节点”而是把每个节点都作为潜在起点记录它第一步往左或往右能走的最远距离。这样穷举所有起点的工作被巧妙地压缩到了一轮遍历里没有减少信息量只是消除了重复计算。从另一个角度看交错路径天然是“自上而下”延伸的起点就是路径中最高的那个节点。它不可能从一个节点下方的子树里升上来再拐弯因为那需要走回父节点而题目限制每一步只能走向子节点。这让“起点枚举”成为一个完整且不重不漏的集合。把每个起点的最优解算出来全局答案自然就是它们的最大值。3. Java 代码实现返回两个值的后序遍历3.1 最推荐的写法理清状态之后代码其实非常短。我比较推荐用后序遍历让每个节点先拿到左右子树的 left/right 状态再组合出当前节点的 left/right。完整代码如下class Solution { private int maxLen; public int longestZigZag(TreeNode root) { maxLen 0; dfs(root); return maxLen; } // 返回长度为 2 的数组 // arr[0] 表示以当前节点为起点第一步向左走的最长交错路径长度 // arr[1] 表示以当前节点为起点第一步向右走的最长交错路径长度。 private int[] dfs(TreeNode node) { if (node null) { return new int[]{0, 0}; } int[] leftInfo dfs(node.left); int[] rightInfo dfs(node.right); // 第一步向左那么之后必须先向右依赖左孩子的“向右状态” int left 0; if (node.left ! null) { left 1 leftInfo[1]; } // 第一步向右那么之后必须先向左依赖右孩子的“向左状态” int right 0; if (node.right ! null) { right 1 rightInfo[0]; } maxLen Math.max(maxLen, Math.max(left, right)); return new int[]{left, right}; } }这段代码里有几个要点值得逐行看。首先是空节点返回 {0, 0}。因为空节点不是一个实际存在的起点它的两个状态都应该是 0这样父节点在组合时不会出现空指针也符合逻辑一个不存在的位置第一步既不可能向左也不可能向右。其次是 left 和 right 的计算位置。我把计算放在递归左右子树之后这是因为 left 和 right 分别依赖左孩子和右孩子已经算好的状态。后序遍历的顺序恰好保证子节点的信息先备齐再回传给父节点整个过程完全不需要额外记忆化数组。最后是全局变量 maxLen 的更新。每个节点算完自己的两个状态后就立刻和全局最大值比较一次。因为答案可能是任意一个节点的 left 或 right所以必须“每到一个节点就比一次”而不是只在根节点处比一次。这个细节很重要初学者最容易漏。3.2 关键边界条件说明有一个边界条件需要反复确认题目返回的是路径的边数不是节点数。对于只有一个节点的树没有边可以走所以最长交错路径长度是 0。上面的代码里单个节点的 left 和 right 都是 0maxLen 保持 0返回结果正确。对于空树也就是 root 为 null 的情况longestZigZag 里 maxLen 被置为 0dfs(root) 会直接返回 {0, 0}最终返回 0。这个结果在 LeetCode 的测试用例里是符合预期的。还有一类边界条件是节点只有左孩子或只有右孩子。比如一个节点只有左孩子那么它的 left 可以继续算right 因为右孩子不存在而为 0。注意这里 right 不能取成一个异常值也不能用 -1 之类的负值去参与最大值的比较否则会把答案带偏。统一用 0 表示“无法走出第一步”是最省心的做法。3.3 不破坏原树的约束怎么满足题目还有一个隐含要求我们只是计算路径长度不能去修改树的结构比如不能在遍历时把某些孩子指针剪掉或者把已经访问过的节点标记成空。上面这份代码完全没有修改 TreeNode 的任何字段只是把计算得到的两个整数抛给上层。所以天然满足“不修改原树”的约束。这一点在面试中值得主动提出来。面试官可能会追问如果树特别大你还要在原树上改来改去风险很高。我的回答是所有信息都封装在 return 值里原树只负责被读取。这样代码的副作用为零也便于封装成一个只读算法工具。3.4 另一种写法带方向的 DFS如果你在网上搜这道题的题解还会看到另一种很常见的写法用一个 dfs(TreeNode node, int direction, int length) 递归其中 direction 表示上一步的方向length 表示当前已经累计的路径长度。递归时如果下一步方向能和上一步交错就把 length 1 往下传如果方向相同就重置 length 为 1。这种写法的优点是直观模拟了“方向交替”的过程但缺点是要在递归参数里额外管理方向和长度逻辑分支比较多。我比较之后还是更推荐“返回两个值”的版本原因有三个。第一返回两个值的版本严格呈现了递推关系代码量少不容易在分支中写漏。第二它天然是后序遍历状态之间依赖清晰阅读者一眼就能看出 left 依赖右状态、right 依赖左状态。第三面试时如果要继续扩展比如打印路径返回两个值的结构也能轻松增加额外信息。当然带方向的 DFS 也是一种有效方案适合喜欢显式模拟状态的人。我建议你两种都理解但如果你时间有限优先把我上面的版本写熟。它几乎就是这题的标准答案。4. 实测踩坑记录与常见问题排查4.1 返回值索引搞反的典型错误我写这道题时第一次提交就翻车了错得非常典型我把数组里两个状态的位置弄反了。代码写成了int left 1 leftInfo[0]; // 错误 int right 1 rightInfo[1]; // 错误看起来好像只是把索引从 1 改成 0、从 0 改成 1为什么不对因为 leftInfo[0] 表示左孩子“第一步向左”的状态不是“第一步向右”的状态。当前节点第一步向左走到左孩子下一步必须向右所以应该使用 leftInfo[1]也就是左孩子“第一步向右”的状态。错误代码会把方向连续两次都取左等于强制走出了“左、左”的非法交错路径结果会比正确答案大或小完全取决于树的形状。排查的方法很简单找一棵只有左子树链的树比如根节点 1 - 左孩子 2 - 左孩子 3。正确结果是 1因为根向左走到 2 后就没法再向左了。如果错误代码把 leftInfo[0] 用上得到 1 (2 的第一步向左长度 1) 2明显超过了合法值。所以我在调试时习惯准备这种“顺序链式”的样例它能非常敏感地暴露方向状态索引写反的问题。4.2 单节点和空树到底返回 0 还是 -1这题有一个容易让人纠结的细节返回的路径长度到底是按边数算还是按节点数算。LeetCode 1372 的原题是按边数算的单节点答案是 0。如果你按照“节点数”理解很可能会把叶子节点状态初始化成 1然后整棵树的答案都会偏大 1导致提交不过。为什么有人会搞混因为很多树的题目在问“最长路径”时会把单节点路径长度定义为 1例如求二叉树直径的那道题路径经过的节点数就是 1。但交错路径这道题的官方定义明确说的是 edges也就是边数。所以你在写代码时所有边界都从 0 起步不要出现任何把空节点状态算成 1 的念头。我个人的习惯是刷题前先看一眼题目的示例和用例。1372 的示例里单节点树给出 0这个信息足够帮你确认初始值。不要想当然套用其他题目的定义。4.3 全局变量为什么不重置我用的是类成员变量 maxLen。在 LeetCode 的评测环境里每个测试用例都会新建一个 Solution 实例所以通常情况下不会出现多个用例之间 maxLen 互相污染的问题。但如果是在本地测试框架里或者在同一个 Solution 实例上连续调用多次 longestZigZag就必须小心了。最稳妥的做法是在 longestZigZag 方法入口处把 maxLen 重置为 0。上面代码里已经写了这行maxLen 0;这是一个非常便宜但非常必要的防御。我有一次在本地写单元测试用同一个 Solution 对象跑了三组测试树结果第二组的结果突然包含了第一组树的答案排查了半天才发现是忘记重置全局变量。从那以后凡是用了全局状态的题目我都会在入口函数第一行做重置。4.4 递归栈溢出和处理办法二叉树递归题还有一个绕不开的问题递归深度。如果这棵树是一条长度为 30000 的链那么后序遍历的递归深度就是 30000JVM 默认栈很可能撑不住会出现 StackOverflowError。在 LeetCode 的测试数据里1372 这道题通常不会给出极端深度的用例但你在本地做压力测试时可能会遇到。如果确实需要处理极端深度可以考虑两个方向。一个是用数组模拟的迭代栈做后序遍历在遍历过程中同时计算每个节点的 left/right但代码会复杂不少另一个是在面试时直接和面试官说明复杂度瓶颈通常面试官考察的是思路而不是为了让你死磕 StackOverflowError。实际工程里如果一棵树的深度达到上万本身就需要考虑递归调用传参或改成非递归的实现这是所有树形递归题共通的限制。4.5 本地自测的构造方法很多读者会问这种树的题目怎么在本地方便地构造测试用例我常用的一个技巧是手写一个根据层序遍历数组建树的方法。比如数组 [1, 2, 3, 4, 5, null, 8]表示节点 1 的左孩子是 2、右孩子是 3节点 2 的左孩子是 4、右孩子是 5节点 3 的左孩子为空、右孩子是 8。用一个队列就能完成建树然后调用 longestZigZag 验证结果。如果你想做更严谨的随机测试可以写一个随机生成树的工具再配合暴力枚举起点的方法做交叉验证。暴力方法虽然慢但结果一定正确用它来校验优化版本是很有效的方案。我自己当时就写了一个 10 万规模的随机树测试把暴力结果和优化结果逐一对拍才敢确认递推公式没有额外问题。5. 复杂度分析、代码调试技巧与面试扩展5.1 时间与空间复杂度核对先说时间复杂度。每个节点在递归过程中只会被访问一次每个节点的操作量是常数级别判断孩子是否为空、取两个数组值、做加法和比较。所以时间复杂度为 O(n)n 是二叉树节点总数。这比暴力枚举起点 O(n²) 的做法提升了一个量级。空间复杂度主要由递归调用栈决定。最坏情况下树的形状是一条链递归深度达到 n因此空间复杂度是 O(n)。如果是一棵完全平衡树递归深度是树的高度 O(log n)空间复杂度则是 O(log n)。总体来说空间复杂度记作 O(h)其中 h 是树高这样能同时覆盖两类情况。很多人在面试时只记得“递归需要 O(n)”却忘了平衡树场景下其实是 O(log n)。说清楚 h 和 n 的关系会让面试官觉得你对递归空间有真正理解。实际上这里没有任何额外的数组或哈希表所以空间完全来自栈帧数清楚这一点就够了。5.2 面试官常见的四个追问第一类追问如果不让用递归只用迭代你怎么实现这个问题考察的是递归和栈的关系。理论上可以用一个显式栈模拟后序遍历对所有节点先入栈再按顺序取出计算。代码会比较长但无非是在迭代遍历的过程中同步维护每个节点的 left/right 信息。对大多数开发岗面试来说能把递归版本说清楚已经足够迭代版本属于加分项。第二类追问如果最长交错路径的起点必须限定在根节点怎么改那就非常简单答案直接取 left[root] 和 right[root] 的最大值即可不再全局比较。这个变体其实比我上面的原版还容易因为它把“任意起点”收敛成了“单一固定起点”。第三类追问如果我要打印出最长交错路径的节点序列而不是只返回长度需要怎么扩展思路是在每个节点的状态里额外保存“方向上那个关键节点”也就是记录 left[u] 依赖 u 的左孩子、right[u] 依赖 u 的右孩子递归保存路径节点。实现时可以引入一个列表在更新 maxLen 时把当前路径的起点和方向序列记录下来。复杂度仍然是 O(n)但额外内存会多一些。第四类追问如果交错路径允许第一步向上走也就是路径可以跨过一个父节点再折返怎么处理这种变体已经脱离了 LeetCode 1372 的原意更像二叉树直径问题。它需要把路径的“折返点”考虑进去状态也不再单纯是“第一步向左/向右”而是要考虑从任意一个节点出发、向上或向下延伸的组合。遇到这种问题我会先把原题思路讲清楚再说明变体为何需要额外设计这本身就是一种展示理解深度的方式。5.3 从长度到路径如果要打印路径怎么改打印路径是一个很好的扩展练习。当前的 maxLen 只记录了一个数字但如果你想知道具体是哪条路径可以在每个节点更新最大值时把当前节点的值以及对应的方向标记记下来。因为 left[u] 对应路径为 u - u.left - …路径上第一个节点是 u第二步方向由 leftInfo[1] 背后的路径决定。严格来说需要在每个节点同时保存“后继节点指针”或“后继方向序列”。以更简单的做法为例可以在递归时返回的不再是 int[2]而是一个对象里面包含 leftLength、leftPath、rightLength、rightPath。虽然会增加不少代码但思路仍然是“状态里多带点信息”。面试时一般不会让你真的写完整版能把方向依赖关系说清楚已经合格。我个人在实际操作中的体会是这题最大的价值不是背住那段十几行代码而是理解“状态怎么定义决定了解法是否自然”。如果你把状态定义成“下一步方向”递推式和代码实现几乎水到渠成如果你把状态定义成“来自哪个方向”后续每一步都要小心地倒推方向很容易把自己绕晕。遇到新的树形 DP 题时先停下来问自己一句这个节点需要向父节点汇报什么信息这才是解决二叉树问题的通用杠杆。希望这篇记录能帮你把 1372 题一次拿下也让你在面试里再遇到交错路径时不急不慌地把整个思路讲明白。