পাইথন ব্যবহার করে ভাল লিফ নোড জোড়ার সংখ্যা খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের একটি বাইনারি গাছ আছে। এবং আরেকটি মান দূরত্ব ঘ. দুটি ভিন্ন লিফ নোডের একটি জোড়াকে ভাল বলা হয়, যখন এই দুটি নোডের মধ্যে সংক্ষিপ্ততম পথটি ছোট বা দূরত্ব d এর মতো হয়।

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

এবং দূরত্ব d =4, তাহলে আউটপুট 2 হবে কারণ জোড়াগুলি (8,7) এবং (5,6) কারণ তাদের পথের দৈর্ঘ্যের দূরত্ব 2, কিন্তু (7,5) বা (8,6) বা অন্যান্য জোড়া ভাল নয় কারণ তাদের পথের দৈর্ঘ্য 5 যা d =4

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

• sol :=0

• একটি ফাংশন util() সংজ্ঞায়িত করুন। এটি রুট নেবে

• যদি রুট শূন্য হয়, তাহলে

  • একটি নতুন তালিকা ফেরত দিন

• যদি মূল হয় পাতা, তাহলে

  • এক জোড়া [0, 0]

    সহ একটি অ্যারে ফেরত দিন

• অন্যথায়,

  • cur :=একটি নতুন তালিকা

  • l :=util(মূলের বামে)

  • r :=util(মূলের ডানদিকে)

  • l এর প্রতিটি n এর জন্য, করুন

    • n[1] :=n[1] + 1

  • প্রতিটি n-এর জন্য r, do

    • n[1] :=n[1] + 1

  • প্রতিটি n-এর জন্য r, do

    • প্রতিটি n1 এর জন্য l, করুন

      • যদি n[1] + n1[1] <=d, তাহলে

        • sol :=sol + 1

  • l+r

    ফেরত দিন

• মূল পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -

• util(root)

• রিটার্ন সল

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

উদাহরণ

class TreeNode:
def __init__(self, val=0, left=None, right=None):
   self.val = val
   self.left = left
   self.right = right
class Solution:
   def __init__(self):
      self.sol = 0
   def solve(self, root, d):
      def util(root):
         if not root:
            return []
         if not root.left and not root.right:
            return [[0, 0]]
         else:
            cur = []
            l = util(root.left)
            r = util(root.right)
            for n in l:
               n[1] += 1
            for n in r:
               n[1] += 1
            for n in r:
               for n1 in l:
                  if n[1] + n1[1] <= d:
                     self.sol += 1
            return l+r
      util(root)
      return self.sol
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.right = TreeNode(4)
root.left.right.left = TreeNode(8)
root.left.right.right = TreeNode(7)
root.right.left = TreeNode(5)
root.right.right = TreeNode(6)
d = 4
ob = Solution()
print(ob.solve(root, d))

ইনপুট

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.right = TreeNode(4)
root.left.right.left = TreeNode(8)
root.left.right.right = TreeNode(7)
root.right.left = TreeNode(5)
root.right.right = TreeNode(6)
d = 4

আউটপুট

2