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


  • 13
    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;
        }
    };

  • 4
    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;
        }
    };

  • 0
    2

    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;
        }
    };

  • 0
    2
    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;
        }
    };

Log in to reply
 

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