Binary Tree Maximum Path Sum

class Solution {

//类似求最大子串，只是数组往一个方向，树往两个方向。

public:

int max_s;

int maxPathSum(TreeNode* root) {

max_s=INT_MIN;

helper(root);

return max_s;

}

int helper(TreeNode* root){

if(!root) return 0;

//只有正数才加，负数不要。

int l=helper(root->left);

int r=helper(root->right);

int temp=root->val;

if(l>0) temp+=l;

if(r>0) temp+=r;

max_s=max(max_s,temp);

return max(l,r)>0? root->val+max(l,r) : root->val;

}

};

class Solution {