Tìm xem cấp độ dọc đã cho của cây nhị phân có được sắp xếp hay không trong Python

Giả sử chúng ta có cây nhị phân; chúng ta phải kiểm tra xem mức độ dọc nhất định của cây nhị phân có được sắp xếp hay không. Khi hai nút chồng lên nhau, hãy kiểm tra xem chúng có theo trình tự được sắp xếp theo cấp độ mà chúng thuộc về không.

Vì vậy, nếu đầu vào giống như l =-1

thì đầu ra sẽ là True, vì các phần tử ở mức -1 là 3,7 và chúng được sắp xếp.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• nếu root là null thì

  • trả về True

• before_value:=-inf

• current_level:=0

• current_node:=một nút cây mới có giá trị 0

• Xác định một dequeue có tên q

• insert (root, 0) vào cuối q

• trong khi q không trống, thực hiện

  • current_node:=q [0, 0]

  • current_level:=q [0, 1]

  • xóa phần tử từ bên trái của q

  • nếu current_level giống với level thì

    • nếu before_value <=current_node.val, thì

      • before_value:=current_node.val

    • nếu không,

      • trả về Sai

  • nếu current_node.left không phải-null thì

    • insert (current_node.left, current_level - 1) vào cuối q

  • nếu current_node.right khác rỗng thì

    • insert (current_node.right, current_level + 1) vào cuối q

• trả về True

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

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)

Đầu ra

True