পাইথনে একটি গাছের বাম গভীরতম নোড খুঁজে বের করার প্রোগ্রাম

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

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

তাহলে আউটপুট 4 হবে কারণ 4 এবং 7 গভীরতম কিন্তু 4 বাকি আছে।

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

• সারি :=একটি নোড রুট সহ একটি সারি।

• left_max :=রুটের মান

• যখন সারির আকার> 0, করুন

  • level_size :=সারির আকার

  • আমি 0 থেকে লেভেল_সাইজের মধ্যে, কর

    • temp :=সারি থেকে প্রথম উপাদান এবং এটি মুছে ফেলুন

    • যদি আমি 0 এর সমান হয়, তাহলে

      • left_max :=তাপমাত্রার মান

    • যদি টেম্পের বামে অ-শূন্য হয়, তাহলে

      • সারির শেষে তাপমাত্রার বামে সন্নিবেশ করুন

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

      • সারির শেষে তাপমাত্রার ডানদিকে সন্নিবেশ করুন

  • বাম_সর্বোচ্চ

    ফেরত দিন

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

উদাহরণ

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

class Solution:
   def solve(self, root):
      queue = [root]
      left_max = root.val
      while len(queue) > 0:
         level_size = len(queue)
         for i in range(level_size):
            temp = queue.pop(0)
            if i == 0:
               left_max = temp.val
            if temp.left:
               queue.append(temp.left)
            if temp.right:
               queue.append(temp.right)
      return left_max
ob = Solution()
root = TreeNode(13)
root.left = TreeNode(12)
root.right = TreeNode(14)
root.right.left = TreeNode(16)
root.right.right = TreeNode(22)
root.right.left.left = TreeNode(4)
root.right.left.right = TreeNode(7)
print(ob.solve(root))

ইনপুট

root = TreeNode(13)
root.left = TreeNode(12)
root.right = TreeNode(14)
root.right.left = TreeNode(16)
root.right.right = TreeNode(22)
root.right.left.left = TreeNode(4)
root.right.left.right = TreeNode(7)

আউটপুট

4