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

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

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

তাহলে আউটপুট রুট থেকে 29 হবে, যদি আমরা 5-<9-<7-<8 পথ অনুসরণ করি তাহলে যোগ করার পরে এটি 29 হবে।

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

একটি ফাংশন ওয়াক () সংজ্ঞায়িত করুন। এটি নোড, এস
নেবে
যদি নোড নাল হয়, তাহলে
- max_sum :=max_sum এবং s
  এর সর্বাধিক
- ফেরত
s :=s + নোডের ডেটা
হাঁটা (নোডের বামে, গুলি)
হাঁটা (নোডের ডানদিকে, গুলি)
মূল পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -
max_sum :=0
walk(root, 0)
সর্বোচ্চ_সমষ্টি ফেরত দিন

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

উদাহরণ

from collections import defaultdict
   class TreeNode:
      def __init__(self, data, left = None, right = None):
         self.data = data
         self.left = left
         self.right = right
   class Solution:
      def walk(self, node, s):
         if not node:
            self.max_sum = max(self.max_sum, s)
         return
      s += node.data
      self.walk(node.left, s)
      self.walk(node.right, s)
   def solve(self, root):
      self.max_sum = 0
      self.walk(root, 0)
   return self.max_sum
ob = Solution()
root = TreeNode(5)
root.left = TreeNode(1)
root.right = TreeNode(9)
root.right.left = TreeNode(7)
root.right.right = TreeNode(10)
root.right.left.left = TreeNode(6)
root.right.left.right = TreeNode(8)
print(ob.solve(root))

ইনপুট

root = TreeNode(5)
root.left = TreeNode(1)
root.right = TreeNode(9)
root.right.left = TreeNode(7)
root.right.right = TreeNode(10)
root.right.left.left = TreeNode(6)
root.right.left.right = TreeNode(8)