পাইথনে একটি বাইনারি গাছে কে-দৈর্ঘ্যের পাথ খুঁজে বের করার জন্য প্রোগ্রাম

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

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

k =3, তাহলে আউটপুট 4 হবে, যেমন পাথগুলি হল [12,8,3], [12,8,10], [8,12,15], [3,8,10]।

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

• একটি ফাংশন dfs() সংজ্ঞায়িত করুন। এটি নোড গ্রহণ করবে

  • যদি নোড নাল হয়, তাহলে

    • 0s

      এর 1 এবং k-1 সংখ্যা সহ একটি তালিকা ফেরত দিন

  • left :=dfs(নোডের বাম দিকে)

  • ডান:=dfs(নোডের ডানদিকে)

  • 0 থেকে K রেঞ্জের জন্য, করুন

    • ans :=ans + left[i] * right[K - 1 - i]

  • res :=0s এর K আকারের একটি তালিকা

  • res[0] :=1, res[1] :=1

  • আমি 1 থেকে K - 1 রেঞ্জের জন্য, কর

    • res[i + 1] :=res[i + 1] + left[i]

    • res[i + 1] :=res[i + 1] + right[i]

  • রিটার্ন রিটার্ন

• প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন−

• উত্তর :=0

• 
  

• dfs(root)

• 
  

• উত্তর ফেরত দিন

  
  

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.data = data
      self.left = left
      self.right = right
class Solution:
   def solve(self, root, K):
      def dfs(node):
         if not node:
            return [1] + [0] * (K-1)
         left = dfs(node.left)
         right = dfs(node.right)
         for i in range(K):
            self.ans += left[i] * right[K - 1 - i]
         res = [0] * K
         res[0] = res[1] = 1
         for i in range(1, K - 1):
            res[i + 1] += left[i]
            res[i + 1] += right[i]
         return res
      self.ans = 0
      dfs(root)
      return self.ans
ob = Solution()
root = TreeNode(12)
root.left = TreeNode(8)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(10)
print(ob.solve(root, 3))

ইনপুট

root = TreeNode(12)
root.left = TreeNode(8)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(10)
3

আউটপুট

4