Pythonで合計がkであるパスの数をカウントするプログラム

二分木と別の値kがあるとすると、合計がkになるサブ子パスへの一意のノードの数を見つける必要があります。

したがって、入力が次のような場合

k =5の場合、パスは[2、3]と[1、4]

これを解決するには、次の手順に従います-

• count：=マップは最初にキー0の値1を保持します
• ans：=0、プレフィックス：=0
• 関数dfs（）を定義します。これはノードを取ります
• ノードがnullでない場合、
  • プレフィックス：=プレフィックス+ノードの値
  • ans：=ans +（count [prefix --target]、これが利用できない場合は0になります）
  • count [prefix]：=count [prefix] + 1
  • dfs（ノードの左側）
  • dfs（ノードの右側）
  • count [prefix]：=count [prefix]-1
  • prefix：=prefix-ノードの値
• メインの方法から、次の手順を実行します
• dfs（root）
• 回答を返す

理解を深めるために、次の実装を見てみましょう-

例

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)
      return ans
     
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