刷题No7 LeetCode Binary Tree Maxim

问题描述：
Given a binary tree, find the maximum path sum.The path may start and end at any node in the tree.For example:Given the below binary tree,
1
/ \
2 3
Return 6.
http://oj.leetcode.com/problems/binary-tree-maximum-path-sum/
参考答案：
http://blog.csdn.net/worldwindjp/article/details/18953987
http://blog.csdn.net/lanxu_yy/article/details/11880189
注意点：
返回类型和结果并不是同一个值。因此为了方便地将结果定义为全局变量。

class Solution {
public:
    /**
     * @param root: The root of binary tree.
     * @return: An integer
     */
    int ans;
    int slovePS(TreeNode *root){
        if(root==NULL) return 0;
        int sum=root->val;
        int lf=0,rf=0;
        if(root->left)
          lf=slovePS(root->left);
        if(root->right)
          rf=slovePS(root->right);
        if(lf>0)
          sum+=lf;
        if(rf>0)
          sum+=rf;// 不可以直接用max函数，因为可能两个都大于0，左右相加
        ans=max(ans,sum);//ans存入结果，并继续进行递归，每次递归计算一下ans
        return max(0,max(lf,rf))+root->val;//递归的结果为从此节点开始最大的路径
    }
    int maxPathSum(TreeNode *root) {
        // write your code here
        if(root==NULL) return 0;//空树返回0
        ans=-0x7fffff;//为方便递归
        slovePS(root);//非空树的值肯定大于-0x7fffff
        return ans;
    }
};