leetcode437. 路径总和 III python_437. 路径总和 iii python3

记录前缀和的解法，一开始只想到了暴力解法

class Solution(object):
    def pathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: int
        """
        self.cnt=0
        currsum=0
        self.presumlist=[]

        def rec(root,sum,currsum):
            if not root:
                return self.cnt
            currsum+=root.val
            if currsum==sum:
                self.cnt+=1
            for presum in self.presumlist:
                if currsum-presum==sum:
                    self.cnt+=1
            self.presumlist.append(currsum)
            rec(root.left,sum,currsum)
            # print(self.presumlist)
            rec(root.right,sum,currsum)
            self.presumlist.pop()
            return self.cnt
        return rec(root,sum,currsum)
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