LeetCode124 二叉树中的最大路径和

 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 };