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

ในบทความนี้เราจะมาดูวิธีการตรวจสอบว่า Binary Tree เรียงลำดับ Level-wise หรือไม่ Level-wise Sorted Binary Tree จะมีลักษณะดังนี้:

ในแต่ละ Level โหนดจะเรียงจากซ้ายไปขวา และแต่ละชั้นจะมีค่ามากกว่าชั้นก่อนหน้า

เราสามารถแก้ปัญหานี้ได้โดยทำ Level Order Traversal และติดตามค่าต่ำสุดและสูงสุดของ Level ปัจจุบัน ใช้ตัวแปร prev_max เก็บค่าสูงสุดของ Level ก่อนหน้า จากนั้นเปรียบเทียบค่าต่ำสุดของ Level ปัจจุบันกับ prev_max หากค่าต่ำสุดมากกว่า prev_max แสดงว่า Tree เรียง Level-wise จนถึง Level นี้ จากนั้นอัปเดต prev_max และค่าสูงสุดของ Level ปัจจุบัน ทำซ้ำจนครบทุก Level

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

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

class Node {
public:
    int key;
    Node *left, *right;
};

Node* getNode(int key) {
    Node* newNode = new Node;
    newNode->key = key;
    newNode->left = newNode->right = NULL;
    return newNode;
}

bool isLevelWiseSorted(Node* root) {
    int prevMax = INT_MIN;
    int min_val, max_val;
    int levelSize;
    queue<Node*> q;
    q.push(root);
    while (!q.empty()) {
        levelSize = q.size();
        min_val = INT_MAX;
        max_val = INT_MIN;
        while (levelSize > 0) {
            root = q.front();
            q.pop();
            levelSize--;
            min_val = min(min_val, root->key);
            max_val = max(max_val, root->key);
            if (root->left)
                q.push(root->left);
            if (root->right)
                q.push(root->right);
        }
        if (min_val <= prevMax)
            return false;
        prevMax = max_val;
    }
    return true;
}

int main() {
    Node* root = getNode(1);
    root->left = getNode(2);
    root->right = getNode(3);
    root->left->left = getNode(4);
    root->left->right = getNode(5);
    root->right->left = getNode(6);
    root->right->right = getNode(7);
    if (isLevelWiseSorted(root))
        cout << "Tree is levelwise Sorted";
    else
        cout << "Tree is Not levelwise sorted";
}

ผลลัพธ์

Tree is level wise Sorted