题目

难度：★★☆☆☆
类型：二叉树

给定一个二叉树，它的每个结点都存放着一个整数值。

找出路径和等于给定数值的路径总数。

路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

二叉树不超过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 的路径有:

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

解答

树的问题用递归实现，设计递归函数：

1. 函数功能

寻找一棵二叉树下所有和为指定值的路径数目。

2. 函数输入输出

函数输入一棵二叉树根节点（node）和一个指定的目标值（sum），函数输出是树下所有和为指定值的路径数目。

3. 函数实现

1. 判断输入的二叉树是否为空树，如果是空树，则直接返回零，因为树中没有任何路径；

2. 判断二叉树的根节点的值（node.val）是否为目标值，如果是目标值，则设置临时变量count为1，否则为零；

3. 寻找左子树和右子树中和为（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)

如有疑问或建议，欢迎评论区留言~