পাইথনে একটি বাইনারি গাছের পাতা এবং নন-লিফ নোড খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের একটি বাইনারি গাছ আছে, আমাদের দুটি সংখ্যার একটি তালিকা খুঁজে বের করতে হবে যেখানে প্রথম সংখ্যাটি গাছের পাতার সংখ্যা এবং দ্বিতীয় সংখ্যাটি নন-লিফ নোডের গণনা৷

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

তাহলে আউটপুট হবে (3, 2), যেহেতু 3টি পাতা এবং 2টি নন-লিফ নোড রয়েছে৷

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

• যদি n শূন্য হয়, তাহলে
  • রিটার্ন (0, 0)
• যদি n-এর বাম অংশ নাল হয় এবং n-এর ডানদিকে শূন্য হয়, তাহলে
  • রিটার্ন (1, 0)
• left :=solve(n-এর বামে)
• ডান :=সমাধান করুন(n এর ডান)
• ফেরত (বাম[0] + ডান[0], 1 + বাম[1] + ডান[1])

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

উদাহরণ

class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.val = data
      self.left = left
      self.right = right
class Solution:
   def solve(self, n):
      if not n:
         return 0, 0
      if not n.left and not n.right:
         return 1, 0
      left, right = self.solve(n.left), self.solve(n.right)
      return left[0] + right[0], 1 + left[1] + right[1]
ob = Solution()
root = TreeNode(6)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.right.left = TreeNode(10)
root.right.right = TreeNode(2)
print(ob.solve(root))

ইনপুট

root = TreeNode(6)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.right.left = TreeNode(10)
root.right.right = TreeNode(2)

আউটপুট

(3, 2)