# 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 {