Khái niệm
Đối với một cây nhị phân nhất định, nhiệm vụ của chúng ta là xác định xem cấp độ dọc nhất định của cây nhị phân có được sắp xếp hay không.
(Đối với trường hợp này, khi hai nút chồng lên nhau, hãy xác minh xem chúng có tạo thành một chuỗi được sắp xếp theo mức độ mà chúng nằm hay không.)
Đầu vào
2 / \ 3 6 / \ 8 5 / 7 Level l = -1
Đầu ra
Yes
Các nút ở mức -1 là 3 -> 7 tạo thành một chuỗi được sắp xếp.
Đầu vào
2 / \ 3 7 \ / 4 5 Level l = 0
Đầu ra
Yes
Cần lưu ý rằng các nút có giá trị 4 và 5 nằm chồng lên nhau trong cây nhị phân.
Bây giờ chúng tôi xác minh xem biểu mẫu này có phải là một cấp trình tự được sắp xếp khôn ngoan hay không. Các nút ở mức 0 là 2 -> 4 -> 5 tạo thành một chuỗi được sắp xếp.
Phương pháp
Theo giải pháp đơn giản, lúc đầu, chúng tôi thực hiện duyệt thứ tự mức của treea và lưu trữ mỗi mức dọc trong các mảng khác nhau. Trong trường hợp này, chúng tôi xác minh xem mảng tương ứng với mức l có được sắp xếp hay không. Cần lưu ý rằng giải pháp này có yêu cầu bộ nhớ lớn có thể được giảm bớt.
Theo giải pháp hiệu quả, chúng tôi thực hiện duyệt theo thứ tự mức dọc của cây nhị phân và duy trì theo dõi các giá trị nút trong mức dọc l của cây nhị phân. Một trình tự đã sắp xếp được tạo ra nếu phần tử trước đó nhỏ hơn hoặc bằng phần tử hiện tại. Tại thời điểm thực hiện duyệt thứ tự mức dọc, lưu trữ giá trị trước đó và so sánh nút hiện tại ở mức thẳng đứng l với giá trị trước đó của mức l. Có thể thấy rằng nếu giá trị nút hiện tại lớn hơn hoặc bằng giá trị trước đó, thì chúng ta phải lặp lại quy trình tương tự cho đến khi kết thúc mức l. Người ta thấy rằng nếu tại bất kỳ giai đoạn nào giá trị nút hiện tại nhỏ hơn giá trị trước đó thì mức l không được sắp xếp. Một lần nữa, người ta quan sát thấy rằng nếu chúng ta đạt đến cuối cấp độ l thì cấp độ sẽ được sắp xếp.
Ví dụ
// CPP program to determine whether
// vertical level l of binary tree
// is sorted or not.
#include <bits/stdc++.h>
using namespace std;
// Shows structure of a tree node.
struct Node1 {
int key1;
Node1 *left1, *right1;
};
// Shows function to create new tree node.
Node1* newNode(int key1){
Node1* temp1 = new Node1;
temp1->key1 = key1;
temp1->left1 = temp1->right1 = NULL;
return temp1;
}
// Indicates helper function to determine if
// vertical level l of given binary
// tree is sorted or not.
bool isSorted1(Node1* root1, int level1){
// So If root is null, then the answer is an
// empty subset and an empty subset is
// always considered to be sorted.
if (root1 == NULL)
return true;
// Indicates variable to store previous
// value in vertical level l.
int prevVal1 = INT_MIN;
// Indicates variable to store current level
// while traversing tree vertically.
int currLevel1;
// Indicates variable to store current node
// while traversing tree vertically.
Node1* currNode1;
// Used to declare queue to do vertical order
// traversal. A pair is used as element
// of queue. The first element in pair
// represents the node and the second
// element represents vertical level
// of that node.
queue<pair<Node1*, int>> q1;
// Used to insert root in queue. Vertical level
// of root is 0.
q1.push(make_pair(root1, 0));
// Perform vertical order traversal until
// all the nodes are not visited.
while (!q1.empty()) {
currNode1 = q1.front().first;
currLevel1 = q1.front().second;
q1.pop();
// Verify if level of node extracted from
// queue is required level or not. If it
// is the required level then verify if
// previous value in that level is less
// than or equal to value of node.
if (currLevel1 == level1) {
if (prevVal1 <= currNode1->key1)
prevVal1 = currNode1->key1;
else
return false;
}
// So if left child is not NULL then push it
// in queue with level reduced by 1.
if (currNode1->left1)
q1.push(make_pair(currNode1->left1, currLevel1 - 1));
// So if right child is not NULL then push it
// in queue with level increased by 1.
if (currNode1->right1)
q1.push(make_pair(currNode1->right1, currLevel1 + 1));
}
// So if the level asked is not present in the
// given binary tree, that means that level
// will contain an empty subset. Therefore answer
// will be true.
return true;
}
// Driver program
int main(){
/*
2
/ \
3 6
/ \
8 5
/
7
*/
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