LeetCode Hard｜124.二叉树中的最大路径和

力扣题目链接
题目解读：
二叉树路径的定义即从1.任意节点出发，到达任意节点；2.该路径至少包含一个节点，且不一定经过跟节点；3.求所有可能路径和的最大值。
也就是说路径途径一个节点只能选择来去两个方向

考虑一个二叉树单元

1. 设计一个函数，它应该能为我们选择左路径还是右路径，所以该函数应该把 a 传入，然后递归调用 b 和 c ，计算 b + a 和 c + a，选择较大的值作为返回值，然后拿到全局最大和。(这里我们很容易确定参数和返回值，并且能够一探递归函数的单层递归逻辑)

2. 需要注意的是，整个路径的最大路径和不一定经过根节点，所以我们的答案并不是根节点的返回值。

3. 这里需要一个能够记录所有路径和中最大值的全局变量，它即为全局最大和。只要我们拿到了刚才的较大路径，应该把它更新到全局最大和中。（确定了一个重要的全局变量）

4. 最后就是选择 左中右，我们在得到 b 和 c 的递归值后计算 b + a + c 的值，如果比“左”和“右”大，就把它更新到全局最大和中。

特别讨论：我们如何处理负数？
我们既然求的事最大和，如果我们把负数囊括进去，对我们的最大和只会是负增益，所以我们应该尽可能舍弃负数，直接用一个 max(0, x)。
注意：1.但是我们的函数中无论是向上连接 b 和 c，a 作为必经之地都是不能舍弃的；2.并且要保证全局最大和的初始值为 INT_MIN。
关于以上两点，我们必须谈到，如果三个节点都是 -1，a 会舍弃掉 b 和 c，但是在返回最终结果时， a 自己是不能被舍弃的，也就是说此时的最大路径和只有 a 自己，即-1。

此时我们可以陆续写一点代码出来了，首先定义我们的递归函数：

int traversal(TreeNode* cur, int& maxSum) {

}

好了，此时我们写我们的主函数：

    int maxPathSum(TreeNode* root) {
        int maxSum = INT_MIN;
        traversal(root, maxSum);
        return maxSum;
    }

最后开始我们的重头戏，递归函数

刚才递归三部曲我们已经走完了第一步：确定函数参数和返回值

第二步：确定终止条件。
这里的终止条件还是比较简单的，就是遇到空节点了返回零：

        if (cur == nullptr) return 0;

第三步：确定单层遍历的逻辑。

还记得我们刚才的思路吗？先去递归找到左右路径选哪个？

        int leftSum = max(0, traversal(cur->left, maxSum));
        int rightSum = max(0, traversal(cur->right, maxSum));

		sum = node->val + max(leftSum, rightSum);

在这里我们不得不说，如果我们选择左右其中的一个，也就说明我们仍然需要往上去遍历，此时我们应该把这个 sum 作为递归函数的返回值返回回去。

        int leftSum = max(0, traversal(cur->left, maxSum));
        int rightSum = max(0, traversal(cur->right, maxSum));

        return cur->val + max(leftSum, rightSum);

好了，我们现在需要选择 左-中-右，此时我们的路已经被选死了，也就是说我们现在应该去处理中间节点（根节点）逻辑。

        int nodeSum = cur->val + leftSum + rightSum;

        maxSum = max(nodeSum, maxSum);

所以递归函数总体的代码是：

        if (cur == nullptr) return 0;

        int leftSum = max(0, traversal(cur->left, maxSum));
        int rightSum = max(0, traversal(cur->right, maxSum));

        int nodeSum = cur->val + leftSum + rightSum;

        maxSum = max(nodeSum, maxSum);

        return cur->val + max(leftSum, rightSum);

总体代码

class Solution {
public:
    int traversal(TreeNode* cur, int& maxSum) {
        if (cur == nullptr) return 0;

        int leftSum = max(0, traversal(cur->left, maxSum));
        int rightSum = max(0, traversal(cur->right, maxSum));

        int nodeSum = cur->val + leftSum + rightSum;

        maxSum = max(nodeSum, maxSum);

        return cur->val + max(leftSum, rightSum);
    }

    int maxPathSum(TreeNode* root) {
        int maxSum = INT_MIN;
        traversal(root, maxSum);
        return maxSum;
    }
};