124.Binary Tree Maximum Path Sum (H)

1.Description(Medium)

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

Example

Given the below binary tree:

  1
 / \
2   3

return6.

2.Code

any to any

时间 O(b^(h+1)-1) 空间 O(h) 递归栈空间 对于二叉树b=2

首先我们分析一下对于指定某个节点为根时，最大的路径和有可能是哪些情况。

第一种是左子树的路径加上当前节点，

第二种是右子树的路径加上当前节点，

第三种是左右子树的路径加上当前节点（相当于一条横跨当前节点的路径），

第四种是只有自己的路径。

乍一看似乎以此为条件进行自下而上递归就行了，然而这四种情况只是用来计算以当前节点根的最大路径，

如果当前节点上面还有节点，那它的父节点是不能累加第三种情况的。所以我们要计算两个最大值，

一个是当前节点下最大路径和，

另一个是如果要连接父节点时最大的路径和。

我们用前者更新全局最大量，用后者返回递归值就行了。

注意最后返回的是currentSum.

public int maxSum=Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root){
        helper(root);
        return maxSum;
    }
    public int helper(TreeNode root){
        if(root==null){
            return 0;
        }
        int left=helper(root.left);
        int right=helper(root.right);
        //连接父节点的最大路径是一、二、四这三种情况的最大值
        int currentSum= Math.max(Math.max(left,right)+root.val,root.val);
        //当前节点的最大路径是一、二、三、四这四种情况的最大值
        int currentMax= Math.max(currentSum,left+right+root.val);
        //用当前最大来更新全局最大
        maxSum=Math.max(maxSum,currentMax);
        return currentSum;
    }

前文 手把手刷二叉树总结篇 说过二叉树的递归分为「遍历」和「分解问题」两种思维模式，这道题需要用到「分解问题」的思维。

这题需要巧用二叉树的后序遍历，可以先去做一下 543. 二叉树的直径 和 366. 寻找二叉树的叶子节点。

oneSideMax 函数和上述几道题中都用到的 maxDepth 函数非常类似，只不过 maxDepth 计算最大深度，oneSideMax 计算「单边」最大路径和：

然后在后序遍历的时候顺便计算题目要求的最大路径和。

class Solution {
    int res = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // 计算单边路径和时顺便计算最大路径和
        oneSideMax(root);
        return res;
    }

    // 定义：计算从根节点 root 为起点的最大单边路径和
    int oneSideMax(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftMaxSum = Math.max(0, oneSideMax(root.left));
        int rightMaxSum = Math.max(0, oneSideMax(root.right));
        // 后序遍历位置，顺便更新最大路径和
        int pathMaxSum = root.val + leftMaxSum + rightMaxSum;
        res = Math.max(res, pathMaxSum);
        // 实现函数定义，左右子树的最大单边路径和加上根节点的值
        // 就是从根节点 root 为起点的最大单边路径和
        return Math.max(leftMaxSum, rightMaxSum) + root.val;
    }
}