পাইথনে বাইনারি ট্রির উল্লম্ব স্তর সাজানো আছে কি না তা খুঁজুন

ধরুন আমাদের বাইনারি ট্রি আছে; বাইনারি গাছের প্রদত্ত উল্লম্ব স্তরটি সাজানো হয়েছে কিনা তা আমাদের পরীক্ষা করতে হবে। যখন দুটি নোড ওভারল্যাপ করা হয়, তখন পরীক্ষা করে দেখুন যে সেগুলি যে স্তরের অন্তর্গত সে অনুযায়ী সাজানো হয়েছে৷

সুতরাং, যদি ইনপুট l =-1

তাহলে আউটপুট হবে True, যেহেতু লেভেল -1-এর উপাদানগুলি হল 3,7 এবং সেগুলি সাজানো হয়েছে৷

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

• যদি রুট শূন্য হয়, তাহলে

  • রিটার্ন ট্রু

• আগের_মান :=-inf

• বর্তমান_স্তর :=0

• current_node :=মান 0

  সহ একটি নতুন ট্রি নোড

• q

  নামে একটি ডিকিউ সংজ্ঞায়িত করুন

• q

  এর শেষে সন্নিবেশ করুন (root, 0)

• q খালি না থাকার সময়, করুন

  • বর্তমান_নোড :=q[0, 0]

  • বর্তমান_স্তর :=q[0, 1]

  • q

    এর বাম থেকে উপাদান মুছুন

  • যদি বর্তমান_স্তর স্তরের সমান হয়, তাহলে

    • যদি পূর্ববর্তী_মান <=current_node.val, তাহলে

      • আগের_মান :=current_node.val

    • অন্যথায়,

      • রিটার্ন ফলস

  • যদি current_node.left নট-নাল হয়, তাহলে

    • Q

      এর শেষে সন্নিবেশ করুন (current_node.left, current_level - 1)

  • যদি current_node.right নন-নাল হয়, তাহলে

    • q এর শেষে সন্নিবেশ করুন (current_node.right, current_level + 1)

• রিটার্ন ট্রু

উদাহরণ

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

from collections import deque
from sys import maxsize
INT_MIN = -maxsize
class TreeNode:
   def __init__(self, key):
      self.val = key
      self.left = None
      self.right = None
def are_elements_sorted(root, level):
   if root is None:
      return True
   previous_value = INT_MIN
   current_level = 0
   current_node = TreeNode(0)
   q = deque()
   q.append((root, 0))
   while q:
      current_node = q[0][0]
      current_level = q[0][1]
      q.popleft()
      if current_level == level:
         if previous_value <= current_node.val:
            previous_value = current_node.val
         else:
            return False
      if current_node.left:
         q.append((current_node.left, current_level - 1))
      if current_node.right:
         q.append((current_node.right, current_level + 1))
   return True
root = TreeNode(2)
root.left = TreeNode(3)
root.right = TreeNode(6)
root.left.left = TreeNode(8)
root.left.right = TreeNode(5)
root.left.right.left = TreeNode(7)
level = -1
print(are_elements_sorted(root, level))

ইনপুট

root = TreeNode(2) root.left = TreeNode(3) root.right = TreeNode(6)
root.left.left = TreeNode(8) root.left.right = TreeNode(5)
root.left.right.left = TreeNode(7)

আউটপুট

True