LeetCode 1372. 二叉树中的最长交错路径

约 6 分钟
文章信息 7 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 LeetCode 75 百度
标签
动态规划 深度优先搜索 树 二叉树

题目描述

✅ 1372. 二叉树中的最长交错路径

image-20260929082521271

image-20260929082521388

image-20260929082521513

题意分析

在二叉树中任选一个节点作为起点，沿孩子边一直向下走，要求相邻两步方向交替为左、右、左、右，或右、左、右、左，求最长路径长度。

长度按边数计算，单个节点长度为零。路径不必从根开始，也不必在叶子结束，但不能向上回到父节点，也不能把两条不同子树的路径拼起来。

解法：显式栈 DFS 维护双方向长度

核心思路

[!blue]

后续能否继续交错取决于最后一步的方向，节点深度或一个不带方向的长度都不够。对当前节点，保存 leftLength 和 rightLength，分别表示以它为终点、最后一步向左或向右的最长交错长度；某个方向没有对应路径时用零表示从当前节点重新开始。

从当前节点走向左孩子时，新路径的最后一步必然向左，前一步必须向右，所以左孩子得到 leftLength = 当前 rightLength + 1。它不可能通过一条向右边结束在这个左孩子，另一状态设为零，用于允许下一步重新起算。走向右孩子时对称，得到 (0, 当前 leftLength + 1)。

如果连续两次走同一方向，父状态中相反方向的长度已经为零，本次相加后就是一，恰好代表从父节点重新开始的一条边，而不会错误延续旧路径。因此无需为每个可能起点重新做搜索。

二叉树中每个节点只有一个父节点，到达它的路径方向由父边唯一决定。将父状态按上述规则传下去，就能得到以每个节点为终点的最佳交错后缀，再在每个节点用两种长度更新全局最大值，覆盖任意起点与终点。

用显式栈保存节点及两项长度，从根的 (0, 0) 开始做深度优先遍历。它与递归传状态作用相同，但不依赖深树下的语言递归调用栈；每个节点只安排一次。

解题步骤

  1. 根为空时返回零；否则将根和两项零长度压栈，答案初值为零。
  2. 弹出一个节点，用它的左右结尾长度更新全局答案。
  3. 左孩子存在时压入 (rightLength + 1, 0)，右孩子存在时压入 (0, leftLength + 1)。
  4. 所有状态处理完成后返回最大边数。

代码实现

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)$。

关键点总结

[!green]

  • 两个状态描述最后一步方向，转移必须交叉使用父节点的相反方向状态。
  • 零状态允许在任意节点重新起步，连续同向边不会接到同一交错路径上。
  • 每个终点都参与全局比较，不只检查根或叶子。
  • 状态记录边数，根和单节点路径从零开始。

易错点总结

[!yellow]

  • 向左仍累加 leftLength，会把连续向左的链误当成交错路径。
  • 未使用方向不归零，会让路径跨过连续同向边继续累加。
  • 只从根统计而不允许中途重新开始，可能漏掉更长的内部交错路径。
  • 把节点数当长度会整体多算一，单节点应返回零。
  • 不能把左右子树两臂相加，本题路径只沿孩子方向向下。

相似题目

题目 难度 关联与区别
978. 最长湍流子数组 中等 同样维护交替方向的连续路径长度，本题方向来自左右孩子，原题来自相邻数值的升降。
543. 二叉树的直径 简单 原题路径可穿过父节点连接两侧，本题是一直向下的交错路径，不能直接拼两条子树臂。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2024/13922938
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！