পাইথনে একটি বাইনারি গাছের সর্বাধিক প্রস্থ খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের একটি বাইনারি গাছ আছে, আমাদের গাছের যেকোনো স্তরের সর্বোচ্চ প্রস্থ বের করতে হবে। এখানে একটি স্তরের প্রস্থ হল নোডের সংখ্যা যা বামতম নোড এবং ডানদিকের নোডের মধ্যে ধরে রাখতে পারে৷

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

এর মত হয়

তাহলে আউটপুট হবে 2

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

একটি মানচিত্র তৈরি করুন d, সর্বনিম্ন এবং সর্বোচ্চ মান ধরে রাখতে, সর্বনিম্ন প্রাথমিকভাবে অসীম এবং সর্বাধিক 0
একটি ফাংশন dfs() সংজ্ঞায়িত করুন। এটি রুট নেবে, pos :=0, গভীরতা :=0
রুট শূন্য হলে, রিটার্ন হবে না
d[গভীরতা, 0] =সর্বনিম্ন d[depth,0] এবং pos
d[গভীরতা, 1] =সর্বাধিক d[গভীরতা,1] এবং pos
dfs(নোডের বামে, 2*pos, depth+1)
dfs(নোডের ডানদিকে, 2*pos+1, depth+1)
প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন−
dfs(root)
mx:=0
d-এর সমস্ত মানের তালিকায় প্রতিটি সর্বনিম্ন-সর্বোচ্চ জোড়ার জন্য করুন
- বাম :=মিনিট, ডানে :=সর্বোচ্চ
- mx:=mx এর সর্বোচ্চ, right-lelf+1
ফিরুন mx

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

উদাহরণ

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 solve(self, root):
   d=defaultdict(lambda: [1e9,0])
   def dfs(node, pos=0, depth=0):
      if not node:
         return
      d[depth][0]=min(d[depth][0],pos)
      d[depth][1]=max(d[depth][1],pos)
      dfs(node.left,2*pos,depth+1)
      dfs(node.right,2*pos+1,depth+1)
   dfs(root)
   mx=0
   for interval in d.values():
      l,r=interval
      mx=max(mx,r-l+1)
   return mx

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)