Kiểm tra xem cấp dọc cho trước của cây nhị phân có được sắp xếp không trong C++

Khái niệm

Cho một cây nhị phân, xác định xem một cấp dọc (vertical level) cho trước của cây có được sắp xếp hay không. (Khi hai nút chồng lên nhau, kiểm tra xem chúng có tạo thành dãy đã sắp xếp ở cấp độ đó hay không).

Đầu vào

2
/ \
3 6
/ \
8 5
/
7
Level l = -1

Đầu ra

Yes

Các nút ở cấp -1 là 3 -> 7 tạo thành dãy đã sắp xếp.

Đầu vào

2
/ \
3 7
\ /
4 5
Level l = 0

Đầu ra

Yes

Các nút giá trị 4 và 5 chồng lên nhau. Kiểm tra cấp 0: 2 -> 4 -> 5 tạo thành dãy đã sắp xếp.

Phương pháp

Giải pháp đơn giản: duyệt theo cấp (level order) và lưu mỗi cấp dọc vào mảng riêng, sau đó kiểm tra mảng của cấp l có sắp xếp không. Nhược điểm: tiêu tốn bộ nhớ lớn.

Giải pháp hiệu quả: duyệt theo thứ tự cấp dọc (vertical level order) và theo dõi giá trị nút ở cấp dọc l. Dãy đã sắp xếp nếu phần tử trước <= phần tử hiện tại. Trong quá trình duyệt, lưu giá trị trước và so sánh với nút hiện tại ở cấp l. Nếu giá trị hiện tại >= giá trị trước, tiếp tục. Nếu tại bất kỳ lúc nào giá trị hiện tại < giá trị trước, cấp l không sắp xếp. Nếu duyệt hết cấp l mà không vi phạm, cấp l đã sắp xếp.

Ví dụ

// CPP xác định cấp dọc l của cây nhị phân có sắp xếp không
#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;
    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;
}

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) == true)
        cout << "Yes";
    else
        cout << "No";
    return 0;
}

Đầu ra

Yes