【LeetCode 热题 100】124. 二叉树中的最大路径和——DFS

Problem: 124. 二叉树中的最大路径和
二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。

整体思路

这段代码旨在解决一个高难度的二叉树问题：二叉树中的最大路径和 (Binary Tree Maximum Path Sum)。这里的“路径”被定义为从树中任意节点到任意节点的序列，路径中至少包含一个节点，且不一定需要经过根节点。

该算法采用了一种精巧的 后序遍历 (Post-order Traversal) 递归思想。算法的核心在于，dfs 递归函数承担了双重职责：

1. 职责一：更新全局最大路径和

   • 在每次访问一个节点 node 时，它都将该节点视为一个潜在的“路径转折点”或“拱顶”。
   • 以 node 为转折点的路径，其最大和可以由 node.val 加上从左子树贡献的最大“向下”路径和 left，再加上从右子树贡献的最大“向下”路径和 right 构成。即 sum = node.val + left + right。
   • 这个 sum 值代表了一个完整的、可能横跨左右子树的路径，它是一个全局最大路径和的候选者。因此，代码用 ans = Math.max(ans, sum) 来随时更新全局最大值 ans。

2. 职责二：向父节点贡献“单边”路径

   • 当 dfs(node) 完成计算后，它需要返回一个值给它的父节点。这个返回值不能是上面计算的“拱形”路径和 sum，因为一条路径不能分叉。
   • 它必须返回一个从 node 出发，一路向下的“单边”路径的最大和。这个单边路径要么走向左子树，要么走向右子树。
   • 因此，它计算 Math.max(left, right) + node.val，选择左右两条单边路径中较大的一条，并加上当前节点的值。
   • 关键的剪枝：如果这个计算出的最佳“单边”路径和是负数，那么它对父节点来说只会起到负面作用。在这种情况下，父节点还不如不包含这条路径。因此，函数最终返回 Math.max(..., 0)，即如果贡献为负，则贡献一个0。

通过这种后序遍历，每个节点都能利用其子节点计算出的“单边最大贡献”，来计算以自身为“拱顶”的全局路径和，并同时计算出能向上贡献给父节点的新的“单边最大贡献”。

完整代码

class Solution {
    // ans: 全局变量，用于存储和更新在整个树中找到的最大路径和。
    // 初始化为整数的最小值，以确保任何路径和（包括负数）都能正确地更新它。
    private int ans = Integer.MIN_VALUE;

    /**
     * 主函数：启动递归计算并返回最终的最大路径和。
     * @param root 树的根节点
     * @return 树中的最大路径和
     */
    public int maxPathSum(TreeNode root) {
        // 调用递归辅助函数，该函数会通过副作用（修改 ans）来计算结果。
        dfs(root);
        // 返回全局最大值。
        return ans;
    }

    /**
     * 递归辅助函数 (DFS)。
     * 该函数有两个职责：
     * 1. 计算以 `node` 为“转折点”的最大路径和，并用它更新全局 `ans`。
     * 2. 返回从 `node` 出发向下的“单边”路径的最大和，作为对父节点的贡献。
     * @param node 当前访问的节点
     * @return 从 `node` 出发的单边路径的最大贡献值（非负）。
     */
    private int dfs(TreeNode node) {
        // 递归的终止条件：如果节点为空，其贡献的路径和为0。
        if (node == null) {
            return 0;
        }
        
        // 后序遍历：先递归计算左右子树的贡献。
        // left: 从左子节点出发的单边路径的最大贡献值（已经过 max(..., 0) 处理，非负）。
        int left = dfs(node.left);
        // right: 从右子节点出发的单边路径的最大贡献值（非负）。
        int right = dfs(node.right);
        
        // 【职责一】计算以当前 node 为“拱顶”的路径和。
        // 这条路径连接了左、右子树贡献的最大单边路径。
        int sum = left + right + node.val;
        // 用这个“拱形”路径和去更新全局最大路径和 ans。
        ans = Math.max(ans, sum);
        
        // 【职责二】计算并返回对父节点的“单边”贡献。
        // 路径不能分叉，所以只能选择左或右中贡献更大的那一条。
        // Math.max(left, right) + node.val 表示从 node 向下的最大单边路径和。
        // 再次与 0 比较，如果这条最佳单边路径的和是负数，就“剪掉”它，向上贡献 0。
        return Math.max(Math.max(left, right) + node.val, 0);
    }
}

时空复杂度

时间复杂度：O(N)

1. 遍历：该算法的核心是深度优先搜索（DFS），它以后序遍历的方式访问树中的每一个节点。
2. 访问次数：每个节点都会被访问且仅被访问一次。
3. 节点操作：在每个节点的访问过程中，执行的都是常数时间的算术运算和 Math.max 操作。
4. 综合分析：
   • 算法由 N 次 O(1) 的操作组成，其中 N 是树中的节点数。
   • 因此，总的时间复杂度是 O(N)。

空间复杂度：O(H)

1. 主要存储开销：该算法的空间开销主要来自于递归调用栈。
2. 递归深度：调用栈的最大深度取决于树的高度 H。
   • 最坏情况：如果树退化成一个链表（Skewed Tree），树的高度 H 等于节点数 N。此时，空间复杂度为 O(N)。
   • 平均/最好情况：如果树是平衡的（Balanced Tree），树的高度 H 约等于 log N。此时，空间复杂度为 O(log N)。

综合分析：
算法的额外辅助空间复杂度由递归栈的深度决定，因此可以统一表示为 O(H)，其中 H 是树的高度。