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

思路

也还是利用深度优先遍历来进行操作。注意，所要求的和不一定需要从根开始。

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
26
27
28
29
30
31
32
33
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution(object):
    def pathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: int
        """
        res = 0
        if (root):
            res += self.search(root, sum)
            if (root.left):
                res += self.pathSum(root.left, sum)
            if (root.right):
                res += self.pathSum(root.right, sum)
        return res
        
    def search(self, node, sum):
        res = 0
        if (node):
            if (sum == node.val):
                res += 1
            if (node.left):
                res += self.search(node.left, sum-node.val)
            if (node.right):
                res += self.search(node.right, sum-node.val)
        return res

Reference: http://xiadong.info/2016/11/leetcode-437-path-sum-iii/