C++, recursive, short, no additional data structure used, brute-force


  • 0
    int pathSum(TreeNode* root, int sum) {
        int count = 0;
        helper(root, sum, count, false);
        return count;
    }
    
    void helper(TreeNode *node, int sum, int &count, bool flag) {
        if (!node) return;
        if (node->val == sum) count++;
        // if the current node gets chosen --> flag will be set to zero in the following recursive calls
        helper(node->left, sum - node->val, count, true);
        helper(node->right, sum - node->val, count, true);
        if (!flag) { // if the flag is already set, we can no longer skip choosing a node
            helper(node->left, sum, count, false);
            helper(node->right, sum, count, false);
        }
    }
    

Log in to reply
 

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