ตรวจสอบ Vertical Level ของ Binary Tree ว่าเรียงลำดับหรือไม่ใน C++

แนวคิด

กำหนด Binary Tree ตรวจสอบว่า Vertical Level ที่กำหนด l เรียงลำดับ (Sorted) หรือไม่ (กรณีโหนดทับซ้อน ให้ดูลำดับใน Level นั้น)

ตัวอย่างที่ 1

Tree: Level l = -1
โหนดใน Level -1: 3 → 7 → Sorted (Yes)

ตัวอย่างที่ 2

Tree: Level l = 0
โหนด 4 และ 5 ทับซ้อนกันใน Level 0
โหนด Level 0: 2 → 4 → 5 → Sorted (Yes)

วิธีแก้ปัญหา

• Simple: Level Order Traversal เก็บแต่ละ Vertical Level เป็นอาร์เรย์ แล้วตรวจสอบว่าเรียงหรือไม่ (ใช้ Memory มาก)
• Efficient: Vertical Level Order Traversal (Queue + Pair) ติดตามค่าก่อนหน้า (prevVal) ใน Level l เฉพาะ ถ้าเจอค่าน้อยกว่า prevVal → ไม่เรียง, จบ Level l ไม่เจอปัญหา → เรียง

โค้ดตัวอย่าง (Efficient)

#include <bits/stdc++.h>
using namespace std;

struct Node1 {
    int key1;
    Node1 *left1, *right1;
};

Node1* newNode(int key1) {
    Node1* temp1 = new Node1;
    temp1->key1 = key1;
    temp1->left1 = temp1->right1 = NULL;
    return temp1;
}

bool isSorted1(Node1* root1, int level1) {
    if (root1 == NULL) return true;  // Empty tree = sorted
    
    int prevVal1 = INT_MIN;
    int currLevel1;
    Node1* currNode1;
    
    queue<pair<Node1*, int>> q1;
    q1.push(make_pair(root1, 0));
    
    while (!q1.empty()) {
        currNode1 = q1.front().first;
        currLevel1 = q1.front().second;
        q1.pop();
        
        if (currLevel1 == level1) {
            if (prevVal1 <= currNode1->key1)
                prevVal1 = currNode1->key1;
            else
                return false;
        }
        
        if (currNode1->left1)
            q1.push(make_pair(currNode1->left1, currLevel1 - 1));
        if (currNode1->right1)
            q1.push(make_pair(currNode1->right1, currLevel1 + 1));
    }
    
    return true;  // Level ไม่มีในต้นไม้ = Empty subset = Sorted
}

int main() {
    Node1* root1 = newNode(2);
    root1->left1 = newNode(3);
    root1->right1 = newNode(6);
    root1->left1->left1 = newNode(8);
    root1->left1->right1 = newNode(5);
    root1->left1->right1->left1 = newNode(7);
    
    int level1 = -1;
    if (isSorted1(root1, level1))
        cout << "Yes";
    else
        cout << "No";
    
    return 0;
}

ผลลัพธ์

Yes