437. 路径总和 III
方法1 爆搜 竟然不超时！~class Solution:
def pathSum(self, root: TreeNode, targetSum: int) -> int:
count = 0
def dfs(root, cur_sum):
if not root:
return
if cur_sum + root.val == targetSum:
nonlocal count
count += 1
dfs(root.left, cur_sum + root.val)
dfs(root.right, cur_sum + root.val)
def preorder(root):
if root:
dfs(root, 0)
preorder(root.left)
preorder(root.right)
else:
return
preorder(root)
return count
方法2 前缀和 dict 换成 collections的dict代码更简洁一些
与 和为K的子数组 一个解法
class Solution:
def pathSum(self, root: TreeNode, targetSum: int) -> int:
pre_map = {0:1}
count = 0
def dfs(root, pre):
if not root:
return
pre += root.val
if pre - targetSum in pre_map:
nonlocal count
count += pre_map[pre - targetSum]
if pre in pre_map:
pre_map[pre] += 1
else:
pre_map[pre] = 1
dfs(root.left, pre)
dfs(root.right, pre)
pre_map[pre] -= 1
dfs(root, 0)
return count
