Kiểm tra cấp dọc của cây nhị phân có được sắp xếp không trong Python

Cho cây nhị phân và cấp dọc (vertical level) l, kiểm tra các nút trên cấp dọc đó có được sắp xếp tăng dần không. Khi nút chồng chéo, kiểm tra thứ tự tại cấp dọc của chúng.

Ví dụ: l = -1, cây có nút 3, 7 tại cấp -1 → True (3, 7 đã sắp xếp).

Thuật toán BFS theo cấp dọc

1. Dùng queue lưu (node, level). Khởi tạo với (root, 0).
2. Biến previous_value = -∞.
3. Khi pop: nếu level == l: kiểm tra previous_value ≤ node.val, cập nhật previous_value. Nếu vi phạm → False.
4. Thêm con trái (level-1) và con phải (level+1) vào queue.
5. Kết thúc → True.

Ví dụ code

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
    q = deque()
    q.append((root, 0))
    while q:
        current_node, current_level = 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))

Input

Cây nhị phân như code, level = -1

Output

True