437. Path Sum III

437. Path Sum III (Medium)

Given the root of a binary tree and an integer targetSum, return the number of paths where the sum of the values along the path equals targetSum.

The path does not need to start or end at the root or a leaf, but it must go downwards (i.e., traveling only from parent nodes to child nodes).

 

Example 1:

Input: root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
Output: 3
Explanation: The paths that sum to 8 are shown.

Example 2:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: 3

 

Constraints:

• The number of nodes in the tree is in the range [0, 1000].
• -109 <= Node.val <= 109
• -1000 <= targetSum <= 1000

Companies:
Facebook, Amazon, Microsoft, Bloomberg, Oracle, Adobe

Related Topics:
Tree, Depth-First Search, Binary Tree

Similar Questions:

• Path Sum (Easy)
• Path Sum II (Medium)
• Path Sum IV (Medium)
• Longest Univalue Path (Medium)

Solution 1. Post-order Traversal

// OJ: https://leetcode.com/problems/path-sum-iii/
// Author: github.com/lzl124631x
// Time: O(N^2)
// Space: O(N^2)
class Solution {
    int ans = 0;
    unordered_map<int, int> dfs(TreeNode *root, int sum) { // map of sums from the current node to a child node
        if (!root) return {};
        unordered_map<int, int> m{{root->val, 1}};
        auto left = dfs(root->left, sum), right = dfs(root->right, sum);
        for (auto &[val, cnt] : left) m[val + root->val] += cnt;
        for (auto &[val, cnt] : right) m[val + root->val] += cnt;
        if (m.count(sum)) ans += m[sum];
        return m;
    }
public:
    int pathSum(TreeNode* root, int sum) {
        dfs(root, sum);
        return ans;
    }
};

Solution 2. Pre-order Traversal

// OJ: https://leetcode.com/problems/path-sum-iii/
// Author: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(H)
class Solution {
private:
    int cnt = 0;
    void pathSum(TreeNode* root, int target, int sum) {
        if (!root) return;
        sum += root->val;
        if (sum == target) cnt++;
        pathSum(root->left, target, sum);
        pathSum(root->right, target, sum);
    }
public:
    int pathSum(TreeNode* root, int sum) {
        if (!root) return 0;
        pathSum(root, sum, 0);
        pathSum(root->left, sum);
        pathSum(root->right, sum);
        return cnt;
    }
};

Or

// OJ: https://leetcode.com/problems/path-sum-iii/
// Author: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(H)
class Solution {
private:
    int pathSum(TreeNode* root, int target, int sum) { // count the paths starting from an acestor node to the current node whose sum equals `target`.
        return root ? ((sum += root->val) == target) + pathSum(root->left, target, sum) + pathSum(root->right, target, sum) : 0;
    }
public:
    int pathSum(TreeNode* root, int sum) {
        return root ? pathSum(root, sum, 0) + pathSum(root->left, sum) + pathSum(root->right, sum) : 0;
    }
}

Solution 3. Pre-order Traversal with Prefix State Map

// OJ: https://leetcode.com/problems/path-sum-iii/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
// Ref: https://leetcode.com/problems/path-sum-iii/discuss/91878/17-ms-O(n)-java-Prefix-sum-method
class Solution {
    unordered_map<int, int> m{{0,1}}; // map from the path sum (from root to the current node) to the corresponding count
public:
    int pathSum(TreeNode* root, int targetSum, int sum = 0) {
        if (!root) return 0;
        sum += root->val;
        int ans = m.count(sum - targetSum) ? m[sum - targetSum] : 0;
        m[sum]++;
        ans += pathSum(root->left, targetSum, sum) + pathSum(root->right, targetSum, sum);
        if (--m[sum] == 0) m.erase(sum);
        return ans;
    }
};