题目：

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 does not need to go through the root.

For example:

Given the below binary tree,

1      / \     2   3

 

Return 6.

思路：

递归

代码：

#include
     
      #include
      
       using namespace std;struct TreeNode{    int val;    TreeNode* left;    TreeNode* right;};int maxPathSum(TreeNode *root,int &maxDist){    if(root==NULL)        return 0;    int lmax=maxPathSum(root->left,maxDist);    int rmax=maxPathSum(root->right,maxDist);    if(lmax+rmax+root->val>maxDist)        maxDist=lmax+rmax+root->val;    return max(0,root->val+max(lmax,rmax));}int main(){    return 0;}