A very concise recursive solution


  • 25
    S
    int maxPathSum(TreeNode *root) {
        int maxPath = INT_MIN;
        dfsMaxPath(root, maxPath);
        return maxPath;
    }
    
    int dfsMaxPath(TreeNode *root, int &maxPath) {
        if (!root) return 0;
        int l = max(0, dfsMaxPath(root->left, maxPath));
        int r = max(0, dfsMaxPath(root->right, maxPath));
        maxPath = max(maxPath, l + r + root->val);
        return root->val + max(l, r);
    }

  • 0
    A

    What is the complexity of this solution? I think the time is O(n), but the recursion makes the space complexity hard to understand.


  • -8
    B

    Your code is nice. only seems" maxPath" is not necessary as an argument. ”maxPath“ is used in l and r before updating in maxPath = max(maxPath, l + r + root->val) , so there is no point considering ”maxPath“ . I modefy your code more intuitive.

    class Solution {
    public:
        int maxPath;
        int maxPathSum(TreeNode *root) {
        maxPath = INT_MIN;
        dfsMaxPath(root);
        return maxPath;
    }
    
    int dfsMaxPath(TreeNode *root) {
        if (!root) return 0;
        int l = max(0, dfsMaxPath(root->left));
        int r = max(0, dfsMaxPath(root->right));
        maxPath = max(maxPath, l + r + root->val);
        return root->val + max(l, r);
    }
    };

  • 0
    S

    @shichaotan I think the answer is wrong if the root is null, it will return INT_MIN


  • 1
    C

    @allbugs said in A very concise recursive solution:

    the time is O(n), but the rec

    You are right. The time complexity is O(n). It is because every node is processed only once.

    To calculate space complexity, let's try to simulate the stack manually for the tree 2->1->3(inoder sequece).

    1. First, root (1) is processed. ie. it is pushed into the stack.
    2. Then, root.left is processed. now stack has 1 and 2.
    3. Then when we do root.left again, it is null and hence we start popping out.
      So at any instance, stack will only contain log n entries. This is for a balanced tree.

    But for worst case space complexity, we usually consider a skewed tree. So considering a left skewed tree, it will contain all n elements in the stack before u start popping out. Therefore, the worst case space complexity would be O(n). Let me know, if it is otherwise.


Log in to reply
 

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