题目：二叉树中的最大路径和

思路：对于任意一个节点，有两件不同的事要做：

  1. 作为贡献值（向上传递）：此时，它只能选择【当前节点值】与【当前节点值 + 左子树贡献值 + 右子树贡献值】中的更大者
  2. 作为拐点（更新全局最大路径和）： 以当前节点为根的局部最大路径和为——当前节点值 + 左子树最大贡献 + 右子树最大贡献，如果之前记录过的最大和小于这个临时的和，就将其覆写

maxPathSum（）

 1class Solution
 2{
 3public:
 4    int maxPathSum(TreeNode* root)
 5    {
 6        pathGain(root);
 7        return maxSum;
 8    }
 9private :
10    int maxSum = INT_MIN;
11    int pathGain(TreeNode* curr)
12    {
13        if(curr == nullptr) return 0;
14
15        // 计算左右子树的最大贡献（不小于零）
16        int left_gain = std::max(pathGain(curr->left), 0);
17        int right_gain = std::max(pathGain(curr->right), 0);
18
19        // 以当前节点为根的最大路径之和
20        int curr_sum = curr->val + left_gain + right_gain;
21
22        // 更新最大值
23        maxSum = std::max(maxSum, curr_sum);
24
25        // 向上传递
26        return curr->val + std::max(left_gain, right_gain);
27    }
28};

原文：hard