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<iostream> #include<stdlib.h> 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; }
原文：http://www.cnblogs.com/AndyJee/p/4896364.html