124. Binary Tree Maximum Path Su

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