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

Level-wise Sorted Binary Tree

Binary Tree ที่ในแต่ละ Level (ความลึก) โหนดเรียงจากซ้ายไปขวา และค่าใน Level ต่อไปมากกว่าค่าสูงสุดของ Level ก่อนหน้า

เงื่อนไข

1. ในแต่ละ Level: ค่าจากซ้ายไปขวา ต้องไม่ลดลง (non-decreasing)
2. ระหว่าง Level: ค่าน้อยที่สุดของ Level ปัจจุบัน > ค่ามากที่สุดของ Level ก่อนหน้า

อัลกอริทึม: Level Order Traversal (BFS)

1. ใช้ Queue ทำ BFS
2. ติดตาม min_val และ max_val ของแต่ละ Level
3. เก็บ prev_max = max_val ของ Level ก่อนหน้า
4. ถ้า min_val ของ Level ปัจจุบัน ≤ prev_max → ไม่เรียง
5. อัปเดต prev_max = max_val

ตัวอย่างโค้ด C++

#include <iostream>
#include <queue>
#include <climits>
#include <algorithm>
using namespace std;

struct Node {
    int data;
    Node *left, *right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

bool isLevelWiseSorted(Node* root) {
    if (!root) return true;
    
    queue q;
    q.push(root);
    int prevMax = INT_MIN;
    
    while (!q.empty()) {
        int levelSize = q.size();
        int minVal = INT_MAX, maxVal = INT_MIN;
        
        for (int i = 0; i < levelSize; i++) {
            Node* curr = q.front(); q.pop();
            minVal = min(minVal, curr->data);
            maxVal = max(maxVal, curr->data);
            
            if (curr->left) q.push(curr->left);
            if (curr->right) q.push(curr->right);
        }
        
        if (minVal <= prevMax) return false;
        prevMax = maxVal;
    }
    return true;
}

int main() {
    // Tree ที่เรียง Level-wise:
    //       1
    //     /   \
    //    2     3
    //   / \   / \
    //  4   5 6   7
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->left = new Node(6);
    root->right->right = new Node(7);
    
    cout << "Tree 1: " << (isLevelWiseSorted(root) ? "Level-wise Sorted" : "Not Level-wise Sorted") << endl;
    
    // Tree ที่ไม่เรียง: Level 2 มี 5, 4 (ไม่เรียงซ้ายขวา)
    Node* root2 = new Node(1);
    root2->left = new Node(3);
    root2->right = new Node(2); // 3, 2 ไม่เรียง
    root2->left->left = new Node(4);
    root2->left->right = new Node(5);
    
    cout << "Tree 2: " << (isLevelWiseSorted(root2) ? "Level-wise Sorted" : "Not Level-wise Sorted") << endl;
    
    return 0;
}

ผลลัพธ์

Tree 1: Level-wise Sorted
Tree 2: Not Level-wise Sorted

ตัวอย่างการตรวจสอบ Tree 1

ความซับซ้อน

• เวลา: O(n) - เยี่ยมชมทุกโหนด 1 ครั้ง
• พื้นที่: O(w) - w = ความกว้างสูงสุดของ tree (queue size)