问题描述：
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;
}
};
