124 二叉树中的最大路径和

一、题目

二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

二、题解

思路：DFS、后序遍历、递归。

1. 核心思路

这道题中的最大路径不一定经过根节点，也不一定从根节点开始。

一条最大路径可能存在于某棵子树中，例如：

       -10
       /  \
      9    20
          /  \
         15   7

最大路径为：

15 -> 20 -> 7

路径和为：

15 + 20 + 7 = 42

对于每个节点，我们需要计算两个不同的结果：

  1. 经过当前节点的最大路径和

    这条路径可以同时连接当前节点的左子树和右子树，用于更新最终答案。

    左子树贡献 + 当前节点值 + 右子树贡献

  2. 当前节点能够向父节点提供的最大贡献

    返回给父节点的路径只能选择左子树或右子树中的一边，否则路径会产生分叉。

    当前节点值 + max(左子树贡献, 右子树贡献)

因此，我们可以使用后序遍历，先计算左右子树的结果，再处理当前节点。

2. 具体步骤

  1. 定义全局变量 maxSum，记录整棵二叉树中的最大路径和。

  2. 使用 dfs(node) 计算从当前节点出发，向下选择一条路径时能够获得的最大路径和。

  3. 递归计算当前节点左右子树提供的最大贡献：

    int leftGain = Math.max(dfs(node.left), 0);
int rightGain = Math.max(dfs(node.right), 0);

  4. 如果某棵子树提供的贡献为负数，就不选择这棵子树，因此将其贡献记为 0。

  5. 计算经过当前节点的完整路径和：

    int currentPathSum = node.val + leftGain + rightGain;

  6. 使用当前路径和更新全局最大值：

    maxSum = Math.max(maxSum, currentPathSum);

  7. 返回当前节点能够提供给父节点的最大贡献：

    return node.val + Math.max(leftGain, rightGain);

  8. 遍历完整棵二叉树后，返回 maxSum。

3. 关键逻辑

3.1 为什么子树贡献要和 0 比较

如果某棵子树提供的路径和为负数，将其加入路径只会让路径和变小。

例如：

    5
   /
 -3

选择左子树时，路径和为：

5 + (-3) = 2

不选择左子树时，路径和为：

5

因此，负数贡献应该直接舍弃：

int leftGain = Math.max(dfs(node.left), 0);
int rightGain = Math.max(dfs(node.right), 0);

3.2 更新答案时可以同时选择左右子树

当当前节点是路径中的最高节点时，路径可以从左子树经过当前节点，再到达右子树：

左子树 -> 当前节点 -> 右子树

因此，经过当前节点的最大路径和为：

int currentPathSum = leftGain + node.val + rightGain;

这个结果用于更新全局最大路径和。

3.3 返回父节点时只能选择一边

假设当前节点还要连接自己的父节点：

           父节点
              |
           当前节点
           /      \
        左子树    右子树

如果当前节点同时选择左右子树，再连接父节点，就会形成三条分支，不再是一条合法路径。

因此，返回给父节点时只能选择左右子树中贡献较大的一边：

return node.val + Math.max(leftGain, rightGain);

3.4 为什么 maxSum 初始化为 Integer.MIN_VALUE

节点值可能全部都是负数，例如：

   -3

如果将 maxSum 初始化为 0，最终答案会错误地变成 0。

但题目规定路径至少包含一个节点，所以正确答案应该是 -3。

因此，需要初始化为：

private int maxSum = Integer.MIN_VALUE;

三、代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *
 *     TreeNode() {}
 *
 *     TreeNode(int val) {
 *         this.val = val;
 *     }
 *
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

class Solution {

    // 记录整棵二叉树中的最大路径和
    private int maxSum = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        // 后序遍历整棵二叉树
        dfs(root);

        // 返回全局最大路径和
        return maxSum;
    }

    /**
     * 返回从当前节点出发，向下选择一条路径时，
     * 当前节点能够向父节点提供的最大路径和。
     */
    private int dfs(TreeNode node) {
        // 1. 处理空节点
        if (node == null) {
            return 0;
        }

        // 2. 递归计算左右子树能够提供的最大贡献
        // 如果贡献为负数，则不选择该子树
        int leftGain = Math.max(dfs(node.left), 0);
        int rightGain = Math.max(dfs(node.right), 0);

        // 3. 计算经过当前节点的完整路径和
        // 这条路径可以同时连接左右子树
        int currentPathSum = leftGain + node.val + rightGain;

        // 4. 更新整棵树的最大路径和
        maxSum = Math.max(maxSum, currentPathSum);

        // 5. 返回给父节点时，只能选择左右子树中的一边
        return node.val + Math.max(leftGain, rightGain);
    }
}

四、复杂度分析

时间复杂度：O(n)O(n)

说明：每个节点只会被递归访问一次，其中 n 是二叉树中的节点数量。

空间复杂度：O(h)O(h)

说明：递归调用栈的深度与二叉树高度 h 有关。

当二叉树接近平衡时，空间复杂度为 O(log⁡n)O(\log n)；当二叉树退化为链表时，空间复杂度为 O(n)O(n)。

评论