437. Path Sum III

來自專欄 leetcode_python刷題_easy題

# Definition for a binary tree node.# class TreeNode(object):# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution(object):# # dfs# def pathSum(self, root, sum):# """# :type root: TreeNode# :type sum: int# :rtype: int# """# if root is None:# return 0# # 分別以不同節點為根節點遍歷# return self.path(root, sum) + self.pathSum(root.left, sum) + self.pathSum(root.right, sum) # def path(self, root, sum):# """# :type root: TreeNode# :type sum: int# :rtype: int# """# num = 0# if root:# if root.val == sum:# num += 1# num += self.path(root.left, sum - root.val)# num += self.path(root.right, sum - root.val)# return num # dfs進一步優化，cache存路徑和及其個數 # 詳見https://leetcode.com/problems/path-sum-iii/discuss/91892/Python-solution-with-detailed-explanation def helper(self, root, target, so_far, cache): if root: complement = so_far + root.val - target if complement in cache: # 找到 self.result += cache[complement] cache.setdefault(so_far+root.val, 0) cache[so_far+root.val] += 1 self.helper(root.left, target, so_far+root.val, cache) self.helper(root.right, target, so_far+root.val, cache) cache[so_far+root.val] -= 1 return def pathSum(self, root, sum): """ :type root: TreeNode :type sum: int :rtype: int """ self.result = 0 self.helper(root, sum, 0, {0:1}) return self.result

推薦閱讀：