Binary Tree Maximum Path Sum
Total Accepted: 14936 Total
Submissions: 75024My Submissions
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
class Solution { public: int maxPathSum(TreeNode *root) { int maxV=0x80000000;////@@@@error: maxV=0; then the negative path sum will be blocked ,since they are smaller than 0. dfs(root,maxV); return maxV; } int dfs(TreeNode *node,int &gMaxV){ int lv=0,rv=0; if(node->left!=NULL) lv=dfs(node->left,gMaxV);//@@@error:no matching function for call to 'Solution::dfs(left)' if(node->right!=NULL) rv=dfs(node->right,gMaxV); gMaxV=max(gMaxV,lv+rv+node->val); return max(0,max(lv,rv)+node->val); } };