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

ধরুন আমাদের একটি বাইনারি ট্রি আছে যেখানে প্রতিটি নোড 0 থেকে 9 পর্যন্ত একটি একক সংখ্যা ধারণ করে। এখন মূল থেকে পাতা পর্যন্ত প্রতিটি পথ ক্রমানুসারে একটি সংখ্যাকে উপস্থাপন করে। আমাদের গাছের সমস্ত পথ দ্বারা উপস্থাপিত সংখ্যার যোগফল খুঁজে বের করতে হবে।

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

তাহলে আউটপুট হবে 680 হিসাবে 46 (4 → 6), 432 (4 → 3 → 2), 435 (4 → 3 → 5), এবং তাদের যোগফল হল 913।

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

একটি ফাংশন সংজ্ঞায়িত করুন solve()। এটি রুট নেবে, স্ট্রিং:=ফাঁকা স্ট্রিং
যদি root এবং root না হয়.left এবং root.right না হয় অ-শূন্য, তাহলে
- রিটার্ন int(string + str(রুটের মান))
মোট :=0
মূলের বাম অংশ শূন্য না হলে
- মোট :=মোট + সমাধানের সাংখ্যিক মান (মূলের বামে, রুটের স্ট্রিং কনক্যাটেনেট মান)
মূলের ডানদিকে যদি শূন্য না হয়, তাহলে
- মোট :=মোট + সমাধানের সংখ্যাসূচক মান(মূলের ডান, রুটের স্ট্রিং কনক্যাটেনেট মান)
মোট রিটার্ন

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

উদাহরণ

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, string=""):
      if root and not root.left and not root.right:
         return int(string + str(root.val))

      total = 0
      if root.left:
         total += int(self.solve(root.left, string + str(root.val)))

      if root.right:
         total += int(self.solve(root.right, string + str(root.val)))

      return total

ob = Solution()
root = TreeNode(4)
root.left = TreeNode(6)
root.right = TreeNode(3)
root.right.left = TreeNode(2)
root.right.right = TreeNode(5)
print(ob.solve(root))

ইনপুট

root = TreeNode(4)
root.left = TreeNode(6)
root.right = TreeNode(3)
root.right.left = TreeNode(2)
root.right.right = TreeNode(5)