题解 | #二叉树的最大路径和#

首先，考虑实现一个简化的函数 maxGain(node)，该函数计算二叉树中的一个节点的最大贡献值，具体而言，就是在以该节点为根节点的子树中寻找以该节点为起点的一条路径，使得该路径上的节点值之和最大。
具体而言，该函数的计算如下。
空节点的最大贡献值等于 0。
非空节点的最大贡献值等于节点值与其子节点中的最大贡献值之和（对于叶节点而言，最大贡献值等于节点值）

例如二叉树：root = [-10,9,20,null,null,15,7]

叶节点 9、15、7 的最大贡献值分别为 9、15、7。
得到叶节点的最大贡献值之后，再计算非叶节点的最大贡献值。节点 20 的最大贡献值等于 20+max(15,7)=35，节点 -10 的最大贡献值等于 −10+max(9,35)=25。
上述计算过程是递归的过程，因此，对根节点调用函数 maxGain，即可得到每个节点的最大贡献值。

根据函数 maxGain 得到每个节点的最大贡献值之后，如何得到二叉树的最大路径和？对于二叉树中的一个节点，该节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值，如果子节点的最大贡献值为正，则计入该节点的最大路径和，否则不计入该节点的最大路径和。维护一个全局变量 maxSum 存储最大路径和，在递归过程中更新 maxSum 的值，最后得到的 maxSum 的值即为二叉树中的最大路径和。

图解：

JAVA版本

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    int maxSum = Integer.MIN_VALUE;
    public int maxPathSum (TreeNode root) {
        // write code here
        maxGain(root);
        return maxSum;
    }
    public int maxGain(TreeNode node) {
        if (node == null) {
            return 0;
        }
        
        // 递归计算左右子节点的最大贡献值
        // 只有在最大贡献值大于 0 时，才会选取对应子节点
        int leftGain = Math.max(maxGain(node.left), 0);
        int rightGain = Math.max(maxGain(node.right), 0);

        // 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
        int priceNewpath = node.val + leftGain + rightGain;

        // 更新答案
        maxSum = Math.max(maxSum, priceNewpath);

        // 返回节点的最大贡献值
        return node.val + Math.max(leftGain, rightGain);
    }
}

Python版本

class Solution:
    def __init__(self):
        self.maxSum = float("-inf")
        
    def maxPathSum(self , root ):
        # write code here
        def maxGain(node):
            if not node:
                return 0
            # 递归计算左右子节点的最大贡献值
            # 只有在最大贡献值大于 0 时，才会选取对应子节点
            leftGain = max(maxGain(node.left), 0)
            rightGain = max(maxGain(node.right), 0)
            
            # 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
            priceNewpath = node.val + leftGain + rightGain
            
            # 更新答案
            self.maxSum = max(self.maxSum, priceNewpath)
        
            # 返回节点的最大贡献值
            return node.val + max(leftGain, rightGain)
        maxGain(root)
        return self.maxSum

复杂度分析

时间复杂度：O(N)，其中 N 是二叉树中的节点个数。对每个节点访问不超过 2 次。
空间复杂度：O(N)，其中 N 是二叉树中的节点个数。空间复杂度主要取决于递归调用层数，最大层数等于二叉树的高度，最坏情况下，二叉树的高度等于二叉树中的节点个数。

算法思想二：深度优先遍历

解题思路：

二叉树：【A,B,C,D,E,null,F】

问题：以A为根节点的这棵树的最大路径和：
单纯的存在于以B为根节点的子树中，单纯的存在于以C为根节点的子树中A节点到达左子树B中某节点的路径，A节点到达右子树C中某节点的路径，左子树B中某节点到达右子树C中某节点的路径，必然经过A节点A节点(假如左、右子树的最大路径均为负数)
因为需要获得从A节点到达其子树中某节点的路径和，所以我们想到深度优先遍历。又因为计算以A为根节点的树的最大路径和计算其子树B、C中的最大路径和函数功能相同，所以同样采用递归算法。

Python版本

class Solution:
    def maxPathSum(self , root ):
        # write code here
        # 初始化 最小值
        res = float('-inf')
        
        def dfs(root):
            nonlocal res
            if not root:
                return float('-inf')
            # 递归左右子树
            left_max = dfs(root.left)
            right_max = dfs(root.right)
            # 分四种情况
            res = max(res, left_max+root.val, right_max+root.val, right_max+left_max+root.val, root.val)
            return max(root.val, root.val+left_max, root.val+right_max)
        # 深度搜索遍历
        dfs(root)
        return res

复杂度分析

时间复杂度：O(N)，其中 N 是二叉树中的节点个数。对每个节点访问不超过 2 次。
空间复杂度：O(N)，其中 N 是二叉树中的节点个数。空间复杂度主要取决于递归调用层数，最大层数等于二叉树的高度，最坏情况下，二叉树的高度等于二叉树中的节点个数。