Problem description:

You are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

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

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

Return 3. The paths that sum to 8 are:

1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11

Solution:

This question we can also use preorder traversal to solve it. That is to say, we visit current node, then check left and right subtree.

We need to maintain a variable pre, to store the sum of previous nodes. If root->cal+pre equal to target, then at least return 1. After that, we still need to check whether if adding other subtree can achieve target(might have zero or negative numbers).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int pathSum(TreeNode* root, int sum) {
        if(!root) return 0;
        //can start from root or left subtree or right subtree
        return helper(root, sum, 0)+ pathSum(root->left, sum)+pathSum(root->right, sum);
    }
    int helper(TreeNode* root, int sum, int pre){
        if(!root) return 0;
        //use pre to store previous levels sum
        //if root->cal+pre equal to target, then at least return 1
        //but still need to check whether if adding other subtree can achieve target(might have zero or negative numbers)
        int cur= pre+ root->val;
        return (cur== sum)+ helper(root->left, sum, cur)+ helper(root->right, sum, cur);
    }
};

time complexity: worst case $O(n^2)$, balanced tree: $T(n) = n + 2T(n/2)$ so $O(n*logn)$

However, previous brute-force solution is more time-consuming. For example 1->3->5, we calculated: 1, 1+3, 1+3+5, 3, 3+5, 5.

  • A more efficient implementation uses the Prefix Sum idea. We use a hash table (extra memory of order N). It would give us an $O(N)$ time complexity.
  • As we traverse down the tree, at an arbitrary node N, we store the sum until this node N (sum_so_far (prefix) + N.val). in hash-table. Note this sum is the sum from root to N.
  • Now at a grand-child of N, say G, we can compute the sum from the root until G since we have the prefix_sum until this grandchild available.We pass in our recursive routine.
  • How do we know if we have a path of target sum which ends at this grand-child G? Say there are multiple such paths that end at G and say they start at A, B, C where A,B,C are predecessors of G. Then sum(root->G) - sum(root->A) = target. Therefore we can compute the complement at G as sum_so_far+G.val-target and look up the hash-table for the number of paths which had this sum
  • Now after we are done with a node and all its grandchildren, we remove it from the hash-table. This makes sure that the number of complement paths returned always correspond to paths that ended at a predecessor node.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def prefixSum(self, root, target, cur, cache):
        if root:
            complement = cur + root.val - target
            if complement in cache:
                self.res += cache[complement]
            cache.setdefault(cur+root.val, 0)
            cache[cur+root.val] += 1
            if root.left:
                self.prefixSum(root.left, target, cur+root.val, cache)
            if root.right:
                self.prefixSum(root.right, target, cur+root.val, cache)
            cache[cur+root.val] -= 1
            
    
    def pathSum(self, root: TreeNode, sum: int) -> int:
        self.res = 0
        self.prefixSum(root, sum, 0, {0:1})
        return self.res

reference:
http://www.cnblogs.com/grandyang/p/6007336.html
https://goo.gl/bYjbbn
https://leetcode.com/problems/path-sum-iii/discuss/91892/Python-solution-with-detailed-explanation
https://leetcode.com/problems/path-sum-iii/discuss/141424/Python-step-by-step-walk-through.-Easy-to-understand.-Two-solutions-comparison.-%3A-)