描述

给定一个二叉树root和一个整数值 sum ，求该树有多少路径的的节点值之和等于 sum 。
1.该题路径定义不需要从根节点开始，也不需要在叶子节点结束，但是一定是从父亲节点往下到孩子节点
2.总节点数目为n
3.保证最后返回的路径个数在整形范围内(即路径个数小于231-1)

数据范围:

0<=n<=10000<=n<=1000
-109 <=节点值<= 109

假如二叉树root为{1,2,3,4,5,4,3,#,#,-1}，sum=6，那么总共如下所示，有3条路径符合要求

示例1

输入：
{1,2,3,4,5,4,3,#,#,-1},6

返回值：3
说明：如图所示，有3条路径符合

示例2

输入：
{0,1},1

返回值：2

示例3

输入：
{1,#,2,#,3},3

返回值：2

代码

注：此题关键是self.n这个全局的计数器。

#coding:utf-8
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @param sum int整型 
# @return int整型
#
class Solution:
    def __init__(self):
        self.n = 0
        
    def FindPath(self , root , sum ):
        # write code here
        if not root:
            return self.n 
        self.help(root, sum)
        self.FindPath(root.left, sum)
        self.FindPath(root.right, sum)
        return self.n 
        
    def help(self, root, sum):
        if not root:
            return 
        sum -= root.val 
        if sum == 0:
            self.n += 1
        self.help(root.left, sum)
        self.help(root.right, sum)