C++ 13ms recursive using a stack

  • 1

    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 {
        vector<int> s;
        int pathSum(TreeNode* root, int sum) {
            if (!root) return 0;
            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++;
            return count;

Log in to reply

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