二叉树中和为某一值的路径(三)

class Solution:
    # 两层递归
    # 时间复杂度：O(n2)  空间复杂度：O(n)
    n = 0
    def recursion(self, root, sum_):
        if not root:
            return 
        if sum_ == root.val:
            self.n += 1 
        self.recursion(root.left, sum_- root.val)  
        self.recursion(root.right, sum_- root.val)  

    def FindPath(self , root: TreeNode, sum_: int) -> int:
        if not root:
            return self.n
        self.recursion(root, sum_)
        # 以其子节点为新根
        self.FindPath(root.left, sum_)
        self.FindPath(root.right, sum_)
        return self.n

class Solution:
    def __init__(self):
        self.mp = {}
    
    def dfs(self, root, sum, lsum):
        if not root:
            return 0
        res = 0
        tmp = root.val + lsum
        if self.mp.__contains__(tmp - sum):
            res += self.mp[tmp - sum]
        if tmp in self.mp:
            self.mp[tmp] += 1
        else:
            self.mp[tmp] = 1
        res += self.dfs(root.left, sum, tmp)
        res += self.dfs(root.right, sum, tmp)
        self.mp[tmp] -= 1
        return res
        
    def FindPath(self , root: TreeNode, sum: int) -> int:
        # write code here
        self.mp[0] = 1
        return self.dfs(root, sum, 0)

class Solution:
    def __init__(self):
        self.count = 0
    def FindPath(self , root: TreeNode, sum: int) -> int:
        hashmaps = {}
        hashmaps[0] = 1
        def getNums(root, prefix):
            if not root:
                return
            prefix = prefix + root.val
            if prefix - sum in hashmaps:
                self.count += hashmaps[prefix - sum]
            if prefix in hashmaps:
                hashmaps[prefix] += 1
            else:
                hashmaps[prefix] = 1
            getNums(root.left, prefix)
            getNums(root.right, prefix)
        getNums(root, 0)
        return self.count

class Solution:
    def FindPath(self , root: TreeNode, sum: int) -> int:
        # write code here
        if not root:
            return 0
        def find(root,target):
            if not root:
                return 0
            all_res=0
            if root.val==target:
                all_res=1
            return find(root.left,target-root.val)+find(root.right,target-root.val)+all_res
        return find(root,sum)+self.FindPath(root.left, sum)+self.FindPath(root.right, sum)

            

每个节点记录当前节点可能的路径和[0, 当前node val, 当前node val+ 父节点val, 当前node val+ 父节点val + 父父节点val ...]
一次dfs即可

class Solution:
    def __init__(self):
        self.res = 0
        
    def CountPath(self , root: TreeNode, now: int) -> int:
        if not root:
            return 0
        if root.val == now:
            return 1 + self.CountPath(root.left, now - root.val) + self.CountPath(root.right, now - root.val)
        else:
            return self.CountPath(root.left, now - root.val) + self.CountPath(root.right, now - root.val)

    def FindPath(self , root: TreeNode, sum: int) -> int:
        # write code here
        if not root:
            return 0
        self.res += self.CountPath(root, sum)
        self.FindPath(root.left, sum)
        self.FindPath(root.right, sum)
        
        return self.res

class Solution:
    # 以root为起始节点可得到的路径数
    def getCount(self, root, count, sum):
        if not root:
            return
        # 这里必须先减去root的值，否则只有一个节点时会出问题
        if sum - root.val == 0:
            count[0] += 1
        self.getCount(root.left, count, sum - root.val)
        self.getCount(root.right, count, sum - root.val)

    def FindPath(self, root: TreeNode, sum: int) -> int:
        if not root:
            return 0
        count = [0]
        self.getCount(root, count, sum)
        res = count[0] + self.FindPath(root.left, sum) + self.FindPath(root.right, sum)
        return res