Binary Tree Maximum Path Sum

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 must contain at least one node and does not need to go through the root.

For example: Given the below binary tree,

1 / \ 2 3 class Solution { public: int maxPathSum(TreeNode* root) { if(!root) return 0; int m=-2147483648; maxPath(root,m); return m; } int maxPath(TreeNode* root,int &m){//这里的m要是引用 if(!root) return 0; int a=maxPath (root->left,m); int b=maxPath(root->right,m); if(a<0) a=0; if(b<0) b=0; if(a+b+root->val>m) m=a+b+root->val; return root->val+max(a,b); } };