题目
难度：★★☆☆☆
类型：二叉树
给定一个二叉树，它的每个结点都存放着一个整数值。
找出路径和等于给定数值的路径总数。
路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。
示例
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
10
/ \
5 -3
/ \ \
3 2 11
/ \ \
3 -2 1
返回 3。和等于 8 的路径有:
- 5 -> 3
- 5 -> 2 -> 1
- -3 -> 11
解答
树的问题用递归实现，设计递归函数：
1. 函数功能
寻找一棵二叉树下所有和为指定值的路径数目。
2. 函数输入输出
函数输入一棵二叉树根节点（node）和一个指定的目标值（sum），函数输出是树下所有和为指定值的路径数目。
3. 函数实现
判断输入的二叉树是否为空树，如果是空树，则直接返回零，因为树中没有任何路径；
判断二叉树的根节点的值（node.val）是否为目标值，如果是目标值，则设置临时变量count为1，否则为零；
寻找左子树和右子树中和为（sum-node.val）的路径数目，该过程通过调用本函数实现，那么输入的二叉树中和为目标值的路径数由三部分组成：
（1）临时变量count；
（2）左子树中和为sum-node.val的路径数；
（3）右子树中和为sum-node.val的路径数；
最终函数返回以上三部分之和。
4. 注意事项
我们在调用本函数时，不仅需要输入根节点，还需要输入需要是根节点的左右子树。
编码实现：
class Solution:
def pathSum(self, root, sum):
def dfs(node, sum):
"""
查找结点node下所有和为sum的路径总个数
:param node:
:param sum:
:return:
"""
if not node: # 如果输入是空树
return 0 # 不论sum是多少，路径数目是零
count = 1 if node.val == sum else 0 # 如果输入树的根节点的值恰好等于sum目标值，那么路径数目加一
# 三条路线的数量和
return count + dfs(node.left, sum - node.val) + dfs(node.right, sum - node.val)
if not root: # 如果输入为空树
return 0 # 返回零
# 三条路线的和
return self.pathSum(root.left, sum) + self.pathSum(root.right, sum) + dfs(root, sum)
如有疑问或建议，欢迎评论区留言~
