Concise C++ prefix-sum solution with explanation


  • 0
    O

    There are two cases when target sum is zero and non-zero, both of them I handle within one line with no branching (read place: ans += ...).

    1.: Non-zero sum case is trivial;

    2.: Zero sum case is less trivial. Consider two subcases:

    2.1.: Path: 2 3 -3. Then prefix sums would be: 2 5 2. So every time number repeats, it means we have zero sum subpath, so number of occurrences - !tsum;

    2.2.: Path: 0 0 1. Then prefix sums would be: 0 0 1. Because I initialized st with 0, we have 3 zeroes, then - !tsum fits here just fine as in 2.1. case. Also initial 0 in st is also needed for non-zero case when subpath with target sum starting from root;

    class Solution {
        void dfs(TreeNode* r, multiset<int>& st, int& ans, int tsum, int sum)
        {
            if(!r) return;
            
            vector<TreeNode*> ch = {r->left, r->right};
            
            int __sum = sum + r->val;
            
            st.insert(__sum);
            
            ans += st.count(__sum - tsum) - !tsum;
            
            for(auto nd : ch) dfs(nd, st, ans, tsum, __sum);
            
            st.erase(st.find(__sum));
        }
        
    public:
        int pathSum(TreeNode* root, int sum)
        {
            multiset<int> st = {0};
            int ans = 0;
                    
            dfs(root, st, ans, sum, 0);
            
            return ans;
        }
    };
    

Log in to reply
 

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