在Python中编写计算路径和为k的路径数量的程序

假设我们有一个二叉树和另一个值k，我们需要找到唯一节点到子节点的路径数，这些路径的总和为k。

因此，如果输入为

并且k = 5，则输出将是2，因为路径为[2,3]和[1,4]

为了解决这个问题，我们将按照以下步骤进行 −

• count：映射，初始设为键0的值为1
• ans：0，prefix：0
• 定义一个dfs()函数。这将采用节点
• 如果节点不为null，则
  • prefix：= 前缀 +节点值
  • 答案：= 答案 +（计数[prefix – target]，如果不存在，则为0）
  • count[prefix]：= count[prefix] + 1
  • dfs（node的左侧）
  • dfs（node的右侧）
  • count[prefix]：= count[prefix] -1
  • prefix：= prefix -节点值
• 在主方法中，执行以下操作
• dfs（root）
• 返回ans

让我们看一下以下实现以更好地理解−

示例

from collections import Counter
class TreeNode:
   def __init__（self, data，left = None，right = None）：
      self.val = data
      self.left = left
      self.right = right

class Solution:
   def solve（self，root，target）：
      count = Counter（[0]）
      ans = prefix = 0

      def dfs（node）：
         nonlocal ans，prefix
         if node：
            prefix + = node.val
            ans + = count[prefix-target]
            count[prefix] + = 1
            dfs（node.left）
            dfs（node.right）

            count[prefix] -= 1
            prefix -= node.val
      dfs（root）
      返回答案
     
ob = Solution()
root = TreeNode（3）
root.left = TreeNode（2）
root.right = TreeNode（4）
root.right.left = TreeNode（1）
root.right.left.right = TreeNode（2）
k = 5
print（ob.solve（root，k））

输入

root = TreeNode(3)
root.left = TreeNode(2)
root.right = TreeNode(4)
root.right.left = TreeNode(1)
root.right.left.right = TreeNode(2)
5

输出

2