C++ Recursive Solution beats 99% WITH explanation

  • 3

    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 {
        int ans = -2147483648;
        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) {
            return ans;

Log in to reply

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