C++ Recursive Solution beats 99% WITH explanation


  • 3
    U

    Basic idea:

    • maxPathDownwards: denotes max sum from the current node downwards including the current node
    • Traverse bottom-up and update ans = max(ans, (max(0, left) + max(0, right) + root->val));, 0 here means we don't use the left/right son's downward path.
    class Solution {
    private:
        int ans = -2147483648;
    public:
        int maxPathDownwards(TreeNode* root) {
            if (!root) return 0;
            int left = maxPathDownwards(root->left);
            int right = maxPathDownwards(root->right);
            ans = max(ans, (max(0, left) + max(0, right) + root->val));
            return root->val + max(0, max(left, right));
        }
        int maxPathSum(TreeNode* root) {
            maxPathDownwards(root);
            return ans;
        }
    };
    

Log in to reply
 

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