[NC]6. 二叉树的最大路径和

🚩传送门：牛客题目
力扣题目

题目

路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。 路径和 是路径中各节点值的总和。

给定一个二叉树的根节点 root ，返回其 最大路径和，即所有路径上节点值之和的最大值。
示例 1：

输入：root = [1,2,3] 输出：6 解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6

示例 2：

输入：root = [-10,9,20,null,null,15,7] 输出：42 解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42

解题思路：递归

对于树的题目，有统一的思考方法，那就是站在树（子树）的顶端根节点root思考。

那么对于此题，我们思考如下问题：如果当前处在root节点，左右节点应该告诉我们什么信息才能得到答案？

根据题中对路径的定义，对于此题我们来回答以上问题。当我们遍历到树中某个节点时，我希望左子节点告诉我，在左子树中，以左子节点为开始（端点）的路径和最大为多少，同理我也希望右子节点告诉我类似的信息。

如果有了以上信息，再来思考最后一个问题：有了这个信息如何得到答案？

显然，对于当前节点有四个选择：

1. 我自己就是一条路径，自己作为路径的结尾结点
2. 只跟左子节点合并成一条路径
3. 只跟右子节点合并成一条路径
4. 以自己为桥梁，跟左、右子节点合并成一条路径

需要注意的是，我们在递归求解的时候，第四种情况是不能作为递归的返回值的，因为它不符合我们对递归所期望返回值的定义（因为此时该子节点并不是拥有最大路径和路径的起点（端点）），但它也是一个可能的解，所以我们用一个全局变量记录上面四种值的最大值，递归结束后，该变量就是答案。

我的代码

class Solution {
    int res = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        getMax(root);
        return res;
    }
    // getMax 返回以该节点为端点的最大路径和
    public int getMax(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int left = getMax(node.left);
        int right = getMax(node.right);
        // 当前节点有4个选择：
        // 1）自己就是一条线
        // 2）跟左子节点合成一条路径 
        // 3）跟右子节点合成一条路径
        int ret = Math.max(node.val, node.val + Math.max(left, right));
        // 4) 跟左右节点一起合成一条路径 （但该值并不应该是遍历的返回值，所以用一个全局遍历记录）
        res = Math.max(res, Math.max(ret, node.val + left + right));
        return ret;
    }
}