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