পাথের সংখ্যা গণনা করার প্রোগ্রাম যার যোগফল পাইথনে k

ধরুন আমাদের একটি বাইনারি ট্রি এবং আরেকটি মান k আছে, আমাদের সাব চাইল্ড পাথের অনন্য নোডের সংখ্যা খুঁজে বের করতে হবে যার যোগফল k হবে।

সুতরাং, যদি ইনপুট মত হয়

এবং k =5, তাহলে আউটপুট হবে 2, যেমন পাথগুলি হল [2, 3] এবং [1, 4]

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

গণনা :=একটি মানচিত্রে প্রাথমিকভাবে কী 0 এর জন্য মান 1 থাকে
উত্তর :=০, উপসর্গ :=০
একটি ফাংশন dfs() সংজ্ঞায়িত করুন। এটি নোড গ্রহণ করবে
যদি নোড নাল না হয়, তাহলে
- উপসর্গ :=উপসর্গ + নোডের মান
- উত্তর :=উত্তর + (গণনা [প্রিফিক্স - টার্গেট], যদি এটি উপলব্ধ না হয় তবে এটি 0 হবে)
- গণনা[উপসর্গ] :=গণনা[উপসর্গ] + ১
- dfs(নোডের বামে)
- dfs(নোডের ডানদিকে)
- গণনা[উপসর্গ] :=গণনা[উপসর্গ] - ১
- উপসর্গ :=উপসর্গ - নোডের মান
মূল পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন
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