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

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

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

তাহলে আউটপুট হবে [27, 18, 3] যেমন কর্ণগুলি [12,15], [8,10], [3]। সুতরাং যোগফলের মান হল [২৭, ১৮, ৩]

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

একটি ফাংশন traverse() সংজ্ঞায়িত করুন। এটি নোড, numLeft, আউটপুট

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

  • ফেরত

• যদি numLeft>=আউটপুটের আকার হয়, তাহলে

  • আউটপুট শেষে নোডের ডেটা সন্নিবেশ করান

• অন্যথায়,

  • আউটপুট[numLeft] :=output[numLeft] + নোডের ডেটা

• যদি নোডের বাম অংশ শূন্য না হয়, তাহলে

  • ট্রাভার্স (নোডের বাম, numLeft+1, আউটপুট)

• যদি নোডের ডানদিকে শূন্য না হয়, তাহলে

  • ট্র্যাভার্স (নোডের ডান, numLeft, আউটপুট)

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

• আউটপুট :=একটি নতুন তালিকা

• ট্রাভার্স(রুট, 0, আউটপুট)

• রিটার্ন আউটপুট

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

উদাহরণ

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):
      output = []
      def traverse(node, numLeft, output):
         if not node:
            return
         if numLeft >= len(output):
            output.append(node.data)
         else:
            output[numLeft] += node.data
         if node.left:
            traverse(node.left, numLeft+1, output)
         if node.right:
            traverse(node.right, numLeft, output)
      traverse(root, 0, output)
      return output
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))

ইনপুট

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

আউটপুট

[27, 18, 3]