LeetCode124 二叉树中的最大路径和

给定一个非空二叉树，返回其最大路径和。

本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

对于每一个节点，计算一个以该节点为根节点，且经过该节点的子树中的最大价值路径，记为maxgain。maxgain等于该节点的值加上左子树的maxgain或0，再加上右子树的maxgain或0；这里在子树maxgain小于0的时候就用0，等于不要这边。得到后用maxgain和当前的最大价值路径比较，然后返回的时候返回的是只加上更大一侧字数的maxgain。

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 private:
12     int maxsum=INT_MIN;
13 public:
14     int maxPathSum(TreeNode* root) {
15         recursive_maxgain(root);
16         return maxsum;
17     }
18 
19     int recursive_maxgain(TreeNode* curNode){
20         if(curNode==nullptr)
21             return 0;
22         int left_gain=recursive_maxgain(curNode->left);
23         int right_gain=recursive_maxgain(curNode->right);
24         int cursum=curNode->val;
25         if(left_gain>0)
26             cursum+=left_gain;
27         if(right_gain>0)
28             cursum+=right_gain;
29         maxsum=max(maxsum,cursum);
30         if(left_gain<0 && right_gain<0)
31             return curNode->val;
32         return curNode->val+max(left_gain,right_gain);
33     }
34 };