题目难度: 中等
今天继续更新 Leetcode 的剑指 Offer(专项突击版)系列, 大家在公众号 算法精选 里回复
剑指offer2
就能看到该系列当前连载的所有文章了, 记得关注哦~
给定一个二叉树的根节点 root ,和一个整数 targetSum ,求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
路径 不需要从根节点开始,也不需要在叶子节点结束,但是路径方向必须是向下的(只能从父节点到子节点)。
sum(5->8->4->1) - sum(5->8)
sumCnt[0] = 1
, 代表路径没有任何节点的情况sumCnt[curSum - targetSum]
, 累加所有节点的这一数目, 就得到了最终结果class Solution:
def pathSum(self, root: TreeNode, targetSum: int) -> int:
# 递归+前缀和计数字典
# sumCnt是前缀和计数字典{curSum:cnt}, 统计当前路径上前缀和是curSum的路径数目cnt
sumCnt = collections.defaultdict(int)
# 显然刚开始时就存在前缀和是0的一种情况, 即空路径
sumCnt[0] = 1
# res记录最终满足条件的路径数目
res = 0
def dfs(node, curSum):
nonlocal res
if not node:
# 当前节点为空, 返回
return
# 更新当前前缀和
curSum += node.val
# 以当前节点为终点的满足条件的路径数目为sumCnt[curSum - targetSum], 累加到最终结果中
res += sumCnt[curSum - targetSum]
# 当前前缀和计数+1, 在遍历子树中可以被用到
sumCnt[curSum] += 1
# 继续递归左右子树
dfs(node.left, curSum)
dfs(node.right, curSum)
# 最后恢复现场, 因为退出当前递归函数后, 当前节点就不在路径上了, 所以其计数要-1
sumCnt[curSum] -= 1
dfs(root, 0)
return res
大家可以在下面这些地方找到我~😊
我的公众号: 算法精选, 欢迎大家扫码关注~😊