Backtrack but seems to be slow


  • 0
    F
    int dfs(TreeNode* node, vector<int> &preSum, int iEnd, int sum)
    {
        int count=0;
        if(node == NULL) return 0;
        if(node->val == sum) count++;
        for(int i=0; i <= iEnd; ++i) {
            preSum[i] += node->val;
            if(preSum[i] == sum) count++;
        }
        preSum[iEnd+1] = node->val;
        count += dfs(node->left, preSum, iEnd+1, sum);
        count += dfs(node->right, preSum, iEnd+1, sum);
        for(int i=0; i<=iEnd; ++i) 
            preSum[i] -= node->val;
        return count;
    }
    
    int pathSum(TreeNode* root, int sum) {
        vector<int> preSum(1000, 0);
        return dfs(root, preSum, -1, sum);
    }

Log in to reply
 

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