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

ধরুন আমাদের একটি বাইনারি গাছ আছে, আমাদের রুট থেকে অ্যালিফ নোড পর্যন্ত দীর্ঘতম পথের যোগফল বের করতে হবে। যদি দুটি একই দীর্ঘ পথ থাকে, তাহলে বড় অঙ্কের সাথে পথটি ফেরত দিন।

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

তাহলে আউটপুট হবে 20।

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

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

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

  • ফেরত (0, 0)

• বড় :=rec-এর সর্বোচ্চ (curr-এর বাম), rec (curr-এর ডানদিকে)

• একটি জোড়া ফেরত দিন (বড়[0] + 1, বড়[1] + curr-এর মান)

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

• ret :=rec(root)

• ret-এর 1ম সূচক ফেরত দিন

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

উদাহরণ

class TreeNode:
   def __init__(self, val, left=None, right=None):
      self.val = val
      self.left = left
      self.right = right

class Solution:
   def solve(self, root):
      def rec(curr):
         if not curr:
            return (0, 0)
         bigger = max(rec(curr.left), rec(curr.right))
         return (bigger[0] + 1, bigger[1] + curr.val)
      return rec(root)[1]
ob = Solution()
root = TreeNode(2)
root.left = TreeNode(10)
root.right = TreeNode(4)
root.right.left = TreeNode(8)
root.right.right = TreeNode(2)
root.right.left.left = TreeNode(6)
print(ob.solve(root))

ইনপুট

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

আউটপুট

20