LeetCode 1372. 二叉树中的最长交错路径
目录
题目描述
题意分析
给定一棵二叉树的根节点，定义「交错路径」为：任选一个起点和一个初始方向（左或右），走到该方向的孩子后必须换成另一个方向，如此左右交替地一直走下去，中途可以随时停下。要返回最长交错路径的长度，而长度的定义是路径上的节点数减一，也就是走过的边数。
三个定义要一起看清。起点任意，不限于根；方向必须严格交替，不能连走两次左；长度按边数计，所以单个节点的交错路径长度是 0 而不是 1。这三条里最容易出错的是第三条——很多人下意识按节点数返回，结果整体偏大 1。
路径的形状值得注意：它不是自顶向下的一条直线，而是「左、右、左、右⋯⋯」的锯齿形，但始终是向下延伸的，不会像求直径那样在某个节点处向两侧拐弯。这意味着一条交错路径完全由「起点 + 首步方向」唯一确定其最大延伸，不需要拼接两段。
约束里节点数最多 $5 \times 10^4$，树可能退化成链。规模是万级，需要线性算法；同时链式退化意味着递归深度可能到 $5 \times 10^4$，要意识到栈空间的量级。
边界要留意四点：树至少有一个节点，不会传入空根；单节点树答案是 0；某个孩子为空时，往那个方向的路径无法迈出第一步；答案要在所有节点上取最大，而不是只看根。
解法：DFS 返回双方向长度
核心思路
交错路径的后续长度不仅取决于节点，还取决于上一条边的方向，因此每个节点需要两个方向状态。经典后序写法让节点返回“向左起步”和“向右起步”的长度；但树可能退化到 5 万层，Java 递归栈存在溢出风险。代码采用等价的显式栈 DFS，自顶向下传递双方向状态。
对栈中的节点定义：
leftLength：以当前节点为终点、最后一步向左的最长交错路径边数；rightLength：以当前节点为终点、最后一步向右的最长交错路径边数。根没有入边，将两个状态都初始化为 0。走向左孩子时，新边方向为左，只能接在“最后一步向右”的路径后，所以左孩子状态为
(rightLength + 1, 0)；走向右孩子时对称地得到(0, leftLength + 1)。另一个方向重置为 0，表示也可以从当前孩子重新开始。循环不变量是：弹出任一状态时，两项都准确描述以该节点为终点、对应最后方向的最长交错路径。每次转移严格按相反方向续接，因此保持不变量。
正确性说明：任意非空交错路径的最后一条边要么向左、要么向右。若最后向左，删掉该边后只可能留下最后向右的交错路径，因此
rightLength + 1是到左孩子的最优值；右侧同理。由根开始归纳，所有节点的两个状态都正确。遍历时对全部状态取最大值，覆盖了任意起点和终点，所以得到全树最长交错路径。
解题步骤
- 根为空时返回 0；否则把
(root, 0, 0)压入显式栈。- 每次弹出节点及其两个方向长度，用二者更新全局答案。
- 若左孩子存在，压入
(leftChild, rightLength + 1, 0)。- 若右孩子存在，压入
(rightChild, 0, leftLength + 1)。- 栈清空后返回答案，长度按边数计算。
对方向序列“左、右、左、右”的链，状态依次增长为 1、2、3、4。对连续两条左边的链，第二条左边不能接在第一条之后，长度会重置为 1。单节点树没有边，答案为 0。显式栈也能安全处理 5 万层退化树。
代码实现
import java.util.ArrayDeque;
import java.util.Deque;
class Solution {
private static class State {
TreeNode node;
int leftLength;
int rightLength;
State(TreeNode node, int leftLength, int rightLength) {
this.node = node;
this.leftLength = leftLength;
this.rightLength = rightLength;
}
}
public int longestZigZag(TreeNode root) {
if (root == null) {
return 0;
}
Deque<State> stack = new ArrayDeque<>();
stack.push(new State(root, 0, 0));
int answer = 0;
while (!stack.isEmpty()) {
State current = stack.pop();
answer = Math.max(
answer, Math.max(current.leftLength, current.rightLength));
if (current.node.left != null) {
stack.push(new State(
current.node.left, current.rightLength + 1, 0));
}
if (current.node.right != null) {
stack.push(new State(
current.node.right, 0, current.leftLength + 1));
}
}
return answer;
}
}
func longestZigZag(root *TreeNode) int {
if root == nil {
return 0
}
type state struct {
node *TreeNode
leftLength, rightLength int
}
stack := []state{{node: root}}
answer := 0
for len(stack) > 0 {
current := stack[len(stack)-1]
stack = stack[:len(stack)-1]
if current.leftLength > answer {
answer = current.leftLength
}
if current.rightLength > answer {
answer = current.rightLength
}
if current.node.Left != nil {
stack = append(stack, state{
node: current.node.Left,
leftLength: current.rightLength + 1,
})
}
if current.node.Right != nil {
stack = append(stack, state{
node: current.node.Right,
rightLength: current.leftLength + 1,
})
}
}
return answer
}
复杂度分析
- 时间复杂度：$O(n)$。每个节点入栈、出栈各一次。
- 空间复杂度：$O(h)$。深度优先栈最多保存与树高同阶的待处理状态；最坏为 $O(n)$，但不占用语言调用栈。
关键点总结
- 状态必须包含方向；只记录节点深度无法判断下一步能否续接。
- 向左走要接
rightLength，向右走要接leftLength，交叉取值就是“方向交替”。- 未被当前边采用的方向要重置为 0，允许从新节点重新开始。
- 答案按边数计算，根和单节点的初始长度都是 0。
- 显式栈保留 DFS 语义，同时规避 5 万层输入导致的递归栈溢出。
易错点总结
- 沿同方向状态续接：全左链会被错误累计成整条路径；走向左孩子只能使用父节点的
rightLength。- 不重置另一个方向：方向序列“左、右、右、左”会把中间连续两次右移错误串起来，得到 3；真实最长交错长度只有 2。
- 把根状态初始化为 1：单节点树会返回 1，而路径长度按边数应为 0。
- 只保存一个方向状态：父节点无法同时判断向左或向右后的可延伸长度，会漏掉左右不对称树中的最优路径。
- 只在根状态上取答案：最长路径可以从任意中间节点开始，必须在每次弹出状态时更新全局最大值。
- 递归处理 5 万层退化树：Java 在常见栈大小下会抛出
StackOverflowError；显式栈不依赖调用栈深度。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 543. 二叉树的直径 | 简单 | 同为「返回值向下、答案全局」的双轨结构，但路径可在节点处向两侧拐弯 |
| 124. 二叉树中的最大路径和 | 困难 | 值可为负，向上返回时要对负贡献取 0，答案仍在每个节点合并左右 |
| 687. 最长同值路径 | 中等 | 延伸条件从「方向交替」换成「值相同」，同样按边数计量 |
| 298. 二叉树最长连续序列 | 中等 | 只能自顶向下递增，状态不需要方向维，适合对比本题为什么必须加方向 |
| 549. 二叉树最长连续序列 II | 中等 | 状态要同时记录递增与递减两个方向的长度，与本题的双分量返回值结构几乎一致 |
| 104. 二叉树的最大深度 | 简单 | 最基础的后序合并，按节点数计量，正好与本题的边数语义形成对照 |
| 110. 平衡二叉树 | 简单 | 返回值兼做「高度」与「是否失衡」两件事，训练返回值语义的设计 |
| 1120. 子树的最大平均值 | 中等 | 返回值要打包「和 + 节点数」两个分量，答案同样在每个节点更新 |
| 979. 在二叉树中分配硬币 | 中等 | 返回值是「盈亏差」，答案累加绝对值，是后序信息上传的另一种典型形态 |
| 968. 监控二叉树 | 困难 | 每个节点有三种状态需要向上传递，是树形 DP 状态维度扩展的进阶版 |
| 333. 最大二叉搜索子树 | 中等 | 返回值要同时携带最值、大小与合法性，考察多分量返回值的组织 |
| 437. 路径总和 III | 中等 | 路径同样起止任意但必须向下，用前缀和哈希把 $O(n^2)$ 压到 $O(n)$ |
| 129. 求根节点到叶节点数字之和 | 中等 | 信息自顶向下传递而非自底向上返回，与本题构成两种递归方向的对照 |
| 863. 二叉树中所有距离为 K 的结点 | 中等 | 需要先补上指向父节点的边把树当成图，说明树上路径题并非都能靠后序解决 |