leetcode 链接：二叉树中的最大路径和

题目

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

给你一个二叉树的根节点 root ，返回其 最大路径和 。

示例：

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

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

解答 & 代码

递归计算二叉树每个节点的最大贡献值 **nodeMaxGain()**（即以该节点为根节点的子树中，以该节点为起点的、节点值之和最大的路径，这条最大路径上的各节点值之和就是最大贡献值），计算步骤如下：

1. 递归结束条件：如果当前节点为空，则对应的最大贡献值为 0，返回 0
2. 递归计算左孩子节点的最大贡献值（若小于 0，则取 0，表示不选取左孩子节点）
3. 递归计算右孩子节点的最大贡献值（若小于 0，则取 0，表示不选取右孩子节点）
4. 计算当前节点的最大贡献值 = 当前节点的值 + 左/右孩子节点的最大贡献值的较大值，并返回

上面计算的每个节点的最大贡献值是以该节点为起点向某个子树方向延伸的路径对应的节点值之和，但对于以该节点为根的子树，并且要求经过该节点的路径中，最大路径和还要加上另一个未使用的孩子节点的贡献值，即最大路径和 = 左孩子节点的最大贡献值 + 当前节点的值 + 右孩子节点的最大贡献值

使用一个变量 maxSum 代表最大路径和，在上述 3、4 步之间插入一步求当前最大路径和（以该节点为根的子树中，并且要求经过该节点的路径中和最大的路径），若当前最大路径和 > maxSum，则更新 maxSum \

总结：核心在于计算结果的时候要计算左右子树，但递归返回的时候只能返回较大的一边

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
private:
    // 递归计算 root 节点的最大贡献值（即以 root 节点为根节点的子树中，以 root 节点为起点的节点值之和最大的路径）
    // maxSum 是二叉树中的最大路径和
    int nodeMaxGain(TreeNode* root, int& maxSum)
    {
        // 递归结束条件：若根节点为空，则最大贡献值为 0
        if(root == nullptr)
            return 0;

        // 递归计算左/右子节点的最大贡献值
        // 如果左/右子节点的最大贡献值小于 0，则不会选取左/右子节点，因此和 0 取 max
        int leftMaxGain = max(nodeMaxGain(root->left, maxSum), 0);
        int rightMaxGain = max(nodeMaxGain(root->right, maxSum), 0);

        // 更新最大路径和（包含当前节点的最大路径和 = 左节点的最大贡献值 + 当前节点值 + 右节点的最大贡献值）
        if(leftMaxGain + root->val + rightMaxGain > maxSum)
            maxSum = leftMaxGain + root->val + rightMaxGain;

        // 返回当前节点的最大贡献值
        return root->val + max(leftMaxGain, rightMaxGain);
    }
public:
    int maxPathSum(TreeNode* root) {
        int maxSum = INT_MIN;
        nodeMaxGain(root, maxSum);
        return maxSum;
    }
};

执行结果：

执行结果：通过

执行用时：28 ms, 在所有 C++ 提交中击败了 73.42% 的用户
内存消耗：26.919.5 MB, 在所有 C++ 提交中击败了 91.37% 的用户