ค้นหาว่ามีการจัดเรียงต้นไม้ไบนารีในระดับแนวตั้งหรือไม่ในPython

สมมติว่าเรามีไบนารีทรี เราต้องตรวจสอบว่าระดับแนวตั้งที่กำหนดของไบนารีทรีนั้นถูกจัดเรียงหรือไม่ เมื่อโหนดสองโหนดซ้อนทับกัน ให้ตรวจสอบว่าโหนดอยู่ในลำดับการเรียงลำดับในระดับที่ตรงกัน

ดังนั้น หากอินพุตเป็น l =-1

จากนั้นผลลัพธ์จะเป็น True เนื่องจากองค์ประกอบในระดับ -1 คือ 3.7 และมีการจัดเรียง

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ถ้ารูทเป็นโมฆะ

  • คืนค่า True

• Previous_value :=-inf

• current_level :=0

• current_node :=โหนดทรีใหม่ที่มีค่า 0

• กำหนดหนึ่ง dequeue ชื่อ q

• แทรก (root, 0) ที่ส่วนท้ายของ q

• ในขณะที่ q ไม่ว่างให้ทำ

  • current_node :=q[0, 0]

  • current_level :=q[0, 1]

  • ลบองค์ประกอบจากด้านซ้ายของ q

  • ถ้า current_level เหมือนกับระดับ แล้ว

    • ถ้า Previous_value <=current_node.val แล้ว

      • Previous_value :=current_node.val

    • มิฉะนั้น

      • คืนค่าเท็จ

  • ถ้า current_node.left ไม่ใช่ค่า null แล้ว

    • แทรก (current_node.left, current_level - 1) ที่ส่วนท้ายของ q

  • ถ้า current_node.right เป็น non-null แล้ว

    • แทรก (current_node.right, current_level + 1) ที่ส่วนท้ายของ q

• คืนค่า True

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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