PAYATHON 2026

如何在线性时间内求二叉树之字形交替和路径的最大值？

数据小许

结论

一次后序遍历即可解决这个问题，时间复杂度为 O(n)，额外空间复杂度为 O(h)，其中 h 是树高。对每个节点，分别记录第一步向左和第一步向右时，交替和的最小值与最大值。遍历完成后，所有节点状态中的最大值就是全树答案。

最小值同样需要保留。父节点接上子路径时，交替和会变成 node.val - childPathSum，因此子路径和越小，父路径和可能越大。

状态与转移

定义 minL、maxL，表示从当前节点出发，下一步向左时（也可以在当前节点结束）路径交替和的最小值与最大值。minR、maxR 表示下一步向右时的对应值。每个方向的状态都包含只经过当前节点的路径，也就是在当前节点停止。

第一步向左到达左孩子后，下一步只能向右，所以左方向状态根据左孩子的右方向状态计算：

maxL = max(node.val, node.val - left.minR)
minL = min(node.val, node.val - left.maxR)

向右时同理，根据右孩子的左方向状态计算：

maxR = max(node.val, node.val - right.minL)
minR = min(node.val, node.val - right.maxL)

如果孩子不存在，对应状态就保持为 node.val，表示路径在当前节点结束。处理每个节点时，用 maxL 和 maxR 更新全局最大值，因此路径起点可以是树中的任意节点。

Java 示例

下面假设 Node 包含 int val、Node left 和 Node right 字段，且输入树非空。状态使用 long，以免路径累加超出 int 范围。

class State {
    long minL, maxL;
    long minR, maxR;

    State(long value) {
        minL = maxL = value;
        minR = maxR = value;
    }
}

class Solver {
    private long best;

    public long maxZigZagSum(Node root) {
        if (root == null) {
            throw new IllegalArgumentException("root must not be null");
        }

        best = Long.MIN_VALUE;
        dfs(root);
        return best;
    }

    private State dfs(Node node) {
        if (node == null) {
            return null;
        }

        State left = dfs(node.left);
        State right = dfs(node.right);
        long value = node.val;
        State current = new State(value);

        if (left != null) {
            // 当前节点向左，左孩子之后必须向右。
            current.maxL = Math.max(value, value - left.minR);
            current.minL = Math.min(value, value - left.maxR);
        }

        if (right != null) {
            // 当前节点向右，右孩子之后必须向左。
            current.maxR = Math.max(value, value - right.minL);
            current.minR = Math.min(value, value - right.maxL);
        }

        best = Math.max(best, Math.max(current.maxL, current.maxR));
        return current;
    }
}

如果接口允许传入空树，应按照调用方的约定为 root == null 指定返回值。空树没有有效路径。

为什么单个“最佳起始路径”状态不够

只记录从节点出发的最大交替和，不足以正确地合并到父节点。父节点的转移是 node.val - childPathSum，子路径和越小，父路径和反而可能越大。只保留子路径的最大值，会丢掉计算父节点最大值所需的信息。因此，至少要同时记录最小值和最大值，并按下一步方向区分状态。

题目中的代码从根节点出发，沿固定的左右交替方向递归，因此只会考虑以根为起点的路径。即使分别尝试两种初始方向，起点仍然是根，无法覆盖树中间的节点。若从每个节点重新启动递归，时间复杂度可能达到 O(n²)。后序遍历只需在每个节点计算常数个状态，再将结果传给父节点。

备注：内容仅供参考。