My recursive solution and analysis


  • 1
    J

    class Solution {

    public:

    typedef map<TreeNode*, int> Map;
    Map M;
    
    int getMaxFromRoot(TreeNode *root)
    {
        if(!root)
            return 0;
        if(M.find(root) != M.end())
            return M[root];
        int ll = getMaxFromRoot(root->left);
        int rr = getMaxFromRoot(root->right);
        if(ll < 0)
            ll = 0;
        if(rr < 0)
            rr = 0;
        return (M[root] = max(ll, rr) + root->val);
    }
    
    int maxPathSum(TreeNode *root) {
        if(!root)
            return 0;
            
        int ll = root->left ? maxPathSum(root->left) : INT_MIN;  // If no left child, then left-child's max-path-sum is INT_MIN
        int rr = root->right ? maxPathSum(root->right) : INT_MIN;
        int max_l = getMaxFromRoot(root->left);
        int max_r = getMaxFromRoot(root->right);
        if(max_l < 0)
            max_l = 0;
        if(max_r < 0)
            max_r = 0;
        M[root] = max(max_l, max_r) + root->val;   // M[root]: the max sum of the path that starts from root (root must be included)
        return max(max(ll, rr), max_l + max_r + root->val);
    }
    

    };

    Idea is simple: max-sum path is either in root's left child tree, or root's right child tree, or the path includes root (passes left and right child tree)


  • 0
    S

    Pay attention to "Writing code? Select all code then click on the {} button to preserve code formatting.” above text editor.


Log in to reply
 

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