📃 题目描述

题目链接：

• 剑指 Offer II 051. 节点之和最大的路径 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)
• 124. 二叉树中的最大路径和 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

🔔 解题思路

主要就是抓住一个点：如果某个节点作为路径的起点，那么就不能同时走到它的左右孩子，只能走其中一边

这里注意区分下某个节点的贡献值（以该节点为【起点】的最大路径和）和最大路径和（以该节点为【拐点】的最大路径和）的概念

比如：

  1
 /  \
2	 3

节点 1 的贡献值（以 1 为起点的最大路径和）是1 + Math.max(1 的左孩子为起点的最大路径和（1 的左孩子的贡献值），以 1 的右孩子为起点的最大路径和（1 的右孩子的贡献值）)= 1, + Math.max(2,3) = 4

而以 1 为拐点的最大路径和是 以 1 的左孩子为起点的最大路径和（1 的左孩子的贡献值） + 1 + 以 1 的右孩子为起点的最大路径和（1 的右孩子的贡献值）

我们的目的就是，找到路径和最大的那个拐点

所以，典型的后序遍历

class Solution {
    // 存储最大路径和
    private int maxSum = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        if (root == null) {
            return 0;
        }

        // 经过当前节点 root 并前往其左子树或右子树的路径的节点值之和的最大值
        maxGain(root);

        return maxSum;
    }

    // 返回 cur 的贡献值（以 cur 为起点的最大路径和）
    private int maxGain(TreeNode cur) {
        if (root == null) {
            return 0;
        }
        
        // 这一段 corner case 可以不写
        // if (cur.left == null && cur.right == null) {
        //     res = Math.max(res, cur.val);
        //     return cur.val;
        // }
        
        // 以 cur.left 为起点的路径和最大值
        // 注意这里不要和 Integer.MIN_VALUE 比较，因为负数也 > MIN_VALUE，但是负数显然对最大路径和没有帮助
        // 所以，只有在最大贡献值大于 0 时，才会选取对应子节点
        int leftGain = Math.max(0, maxGain(cur.left));
        // 以 cur.right 为起点的路径和最大值
        int rightGain = Math.max(0, maxGain(cur.right));
        
        // 以 cur 为拐点的路径和
        int sum = leftGain + cur.val + rightGain;
        // 最大路径和
        maxSum = Math.max(maxSum, sum);
		
        // 返回 cur 的贡献值（以 cur 为起点的最大路径和）
        return cur.val + Math.max(leftGain, rightGain);
    }
}

💥 复杂度分析

• 空间复杂度：O(LogN)，取决于树的高度
• 时间复杂度：O(N)，对每个节点访问不超过 2 次