Given a binary tree, find the maximum path sum.
For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.
For example:Given the below binary tree,
1
/ \
2 3
Return 6.
class Solution {
public:
int dfs(TreeNode* root)
{
if(root==NULL)
return 0;
int l = dfs(root->left);
int r = dfs(root->right);
int sum = root->val;
if(l>0)
sum += l;
if(r>0)
sum += r;
max_sum = max(max_sum,sum);
return max(r,l) > 0 ? max(r,l) + root->val : root->val;
//最后return的时候，只返回一个方向的值，因为在递归中，只能向父节点返回，不可能存在L->root->R的路径，只可能是L->root或者R->root
}
int max_sum;
int maxPathSum(TreeNode* root) {
max_sum = INT_MIN;
dfs(root);
return max_sum;
}
};
