পাইথনে বাইনারি গাছের সর্বোচ্চ গভীরতা

ধরুন আমাদের একটি বাইনারি গাছ আছে। আমাদের সেই গাছের সর্বোচ্চ গভীরতা খুঁজে বের করতে হবে। একটি গাছের সর্বোচ্চ গভীরতা হল সর্বাধিক সংখ্যক নোড যা দীর্ঘতম পথ ব্যবহার করে মূল থেকে পাতায় পৌঁছানোর জন্য অতিক্রম করা হয়। ধরুন গাছটি নিচের মত। গভীরতা এখানে 3 হবে।

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

• এখানে আমরা পুনরাবৃত্তিমূলক পদ্ধতি ব্যবহার করব। পদ্ধতি হল সমাধান(root, depth =0)
• যদি রুট খালি থাকে, তাহলে গভীরতা ফেরত দিন
• অন্যথায় সমাধানের সর্বোচ্চ (বাম, গভীরতা + 1) এবং সমাধান (বাম, গভীরতা + 1) ফেরত দিন

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

উদাহরণ

class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.data = data
      self.left = left
      self.right = right
def insert(temp,data):
   que = []
   que.append(temp)
   while (len(que)):
      temp = que[0]
      que.pop(0)
      if (not temp.left):
         if data is not None:
            temp.left = TreeNode(data)
         else:
            temp.left = TreeNode(0)
         break
      else:
         que.append(temp.left)
      if (not temp.right):
         if data is not None:
            temp.right = TreeNode(data)
         else:
            temp.right = TreeNode(0)
         break
      else:
         que.append(temp.right)
def make_tree(elements):
   Tree = TreeNode(elements[0])
   for element in elements[1:]:
      insert(Tree, element)
   return Tree
class Solution(object):
   def maxDepth(self, root):
      """
      :type root: TreeNode
      :rtype: int
      """
      return self.solve(root)
   def solve(self,root,depth = 0):
      if root == None:
         return depth
      return max(self.solve(root.left,depth+1),self.solve(root.right,depth+1))
tree1 = make_tree([1,2,2,3,4,None,3])
ob1 = Solution()
print(ob1.maxDepth(tree1))

ইনপুট

tree1 = make_tree([1,2,2,3,4,None,3])

আউটপুট

3