题目：
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.
代码如下：
int max;
int getmax(TreeNode *root)
{
int t1=root->val;
int t2=t1;
int nleft=0,nright=0;
if(root->left!=NULL)
{
nleft=getmax(root->left);
if(nleft<0)nleft=0;
}
if(root->right!=NULL)
{
nright=getmax(root->right);
if(nright<0)nright=0;
}
t1+=nleft>nright nleft:nright;
t2+=nleft+nright;
if(t2>max)max=t2;
return t1;
}
int maxPathSum(TreeNode *root) {
if(root==NULL)return 0;
max=-99999;
getmax(root);
return max;
}