C++ 13ms recursive using a stack


  • 1
    A

    C++ 13ms solution using a stack (not exactly a stack as we iterate through it)
    Time complexity: O(nlogn)
    Space complexity: O(logn)

    class Solution {
    public:
        vector<int> s;
        int pathSum(TreeNode* root, int sum) {
            if (!root) return 0;
            s.push_back(root->val);
            int count = pathSum(root->left, sum) + pathSum(root->right, sum);
            int tmp_sum = 0;
            for(int i = s.size()-1 ; i >= 0 ; i--) {
                tmp_sum += s[i];
                if (tmp_sum == sum) count++;
            }
            s.pop_back();
            return count;
        }
    };
    

Log in to reply
 

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