ตรวจสอบระดับแนวตั้งของ Binary Tree ว่าเรียงลำดับหรือไม่ (Python)

โจทย์: กำหนด Binary Tree และ vertical level l ตรวจสอบว่าโหนดในระดับนั้นเรียงจากบนลงล่าง (ตาม level order) หรือไม่

ตัวอย่าง: level -1 มีโหนด 3, 7 → เรียงแล้ว → True

อัลกอริทึม BFS + Vertical Level Tracking

1. BFS (queue) พร้อมเก็บ (node, level)
2. root อยู่ level 0, left child = level-1, right child = level+1
3. ตอน dequeue: ถ้า level == target → ตรวจสอบค่ากับ previous_value (ต้อง ≥)
4. ถ้าเจอค่าลดลง → False
5. จบลูปไม่เจอ → 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
    prev_val = INT_MIN
    q = deque()
    q.append((root, 0))
    while q:
        node, curr_level = q.popleft()
        if curr_level == level:
            if prev_val <= node.val:
                prev_val = node.val
            else:
                return False
        if node.left:
            q.append((node.left, curr_level - 1))
        if node.right:
            q.append((node.right, curr_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)

print(are_elements_sorted(root, -1))  # True

ผลลัพธ์

True

สรุป: BFS ติดตาม vertical level O(n) time O(n) space (queue) ตรวจสอบลำดับในระดับเป้าหมายแบบ streaming ไม่ต้องเก็บทั้งระดับ