Kiểm tra cây nhị phân có được sắp xếp theo cấp độ trong C++

Chúng ta sẽ kiểm tra một cây nhị phân có được sắp xếp theo cấp độ (level-wise sorted) hay không. Cây level-wise sorted có đặc điểm: tại mỗi cấp độ, các nút được sắp xếp tăng dần từ trái sang phải, và giá trị nhỏ nhất của cấp độ hiện tại lớn hơn giá trị lớn nhất của cấp độ trước.

Giải pháp: thực hiện duyệt theo cấp độ (level order traversal), theo dõi giá trị min và max của cấp độ hiện tại. Dùng biến prevMax lưu max của cấp độ trước. Nếu min_val > prevMax thì cây sorted đến cấp độ này. Cập nhật prevMax = max_val và tiếp tục.

Ví dụ

#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";
}

Kết quả

Tree is level wise Sorted