# [recommend for beginners]clean C++ implementation with detailed explanation

• ``````class Solution {
int sum;
public:
int maxPathSum(TreeNode* root) {
sum=INT_MIN;
help(root);
return sum;
}

/*** return the max-value-ended-at-root-node ***/
int help(TreeNode* root){
if(!root)   return 0;
int left = max(0, help(root->left));
int right = max(0, help(root->right));
/*** key parts : embedding the max-value-find in the recursion process ***/
sum = max(sum, left+right+root->val);
/*** get the max-value-ended-at-root ***/
return max(left, right)+root->val;
}
};``````

• ``````class Solution {
public:
int maxPathSum(TreeNode* root) {
int result=INT_MIN;
help(root, result);
return result;
}

int help(TreeNode* root, int& result){
if(!root)    return 0;
int left=max(0, help(root->left, result));
int right=max(0, help(root->right, result));
result=max(result, left+right+root->val);
return max(left, right)+root->val;
}
};``````

• This problem is really tricky ....

``````class Solution {
int sum=INT_MIN;
public:
int maxPathSum(TreeNode* root) {
help(root);
return sum;
}

int help(TreeNode* root) {
if(!root)  return 0;
int left = max(0, help(root->left));
int right = max(0, help(root->right));
sum = max(sum, left + right + root->val);
return max(left, right) + root->val;
}
};``````

• ``````class Solution {
int result = INT_MIN;
public:
int maxPathSum(TreeNode* root) {
help(root);
return result;
}

/*** store the max val ended at the root node **/
int help(TreeNode* root) {
if(!root)  return 0;
/** we should check whether the path-sum bigger than 0 **/
int left = max(0, help(root->left));
int right = max(0, help(root->right));
result = max(result, left + right + root->val);
// result = max(result, left + root->val);
// result = max(result, right + root->val);
return max(left, right) + root->val;
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.