给定一个二叉树的根节点 root ,和一个整数 targetSum ,求该二叉树里节点值之和等于 targetSum 的 路径 的数目。 路径 不需要从根节点开始,也不需要在叶子节点结束,但是路径方向必须是向下的(只能从父节点到子节点)。
时间: 2024-02-09 10:10:22 浏览: 86
好的,这是一道二叉树路径相关的问题,我可以帮你解答。这里给出一种递归的解法:
对于每个节点,我们可以分别计算从该节点出发的路径数目,然后将其累加起来即可得到整棵树中路径数目。
具体而言,设递归函数 pathSum(node, target) 表示从节点 node 出发,和为 target 的路径数目。我们可以分为两种情况进行讨论:
1. 从当前节点出发的路径满足条件:此时路径数目加一,然后递归计算左右子树中和为 target - node.val 的路径数目。
2. 从当前节点出发的路径不满足条件:直接递归计算左右子树中和为 target - node.val 的路径数目。
最后,我们对根节点调用 pathSum(root, targetSum) 即可得到整棵树中路径数目。
具体实现可以参考以下代码(代码中的 sum_list 是一个列表,用于记录每个节点的前缀和):
```python
def pathSum(root, targetSum):
sum_list = [0] # 初始化前缀和列表
return dfs(root, sum_list, targetSum)
def dfs(node, sum_list, targetSum):
if not node: # 递归终止条件
return 0
count = 0
cur_sum = sum_list[-1] + node.val # 计算当前节点的前缀和
for i in range(len(sum_list)):
if cur_sum - sum_list[i] == targetSum: # 满足条件1
count += 1
sum_list.append(cur_sum) # 将当前节点的前缀和加入列表
count += dfs(node.left, sum_list, targetSum) # 递归计算左子树
count += dfs(node.right, sum_list, targetSum) # 递归计算右子树
sum_list.pop() # 回溯,将当前节点的前缀和从列表中弹出
return count
```
希望能够帮到你!
阅读全文