컨셉
주어진 이진 트리와 관련하여 우리의 임무는 주어진 수직 수준의 이진 트리가 정렬되었는지 여부를 결정하는 것입니다.
(이 경우 두 개의 노드가 겹칠 경우 해당 노드가 위치한 레벨에서 정렬된 시퀀스를 형성하는지 확인합니다.)
입력
2 / \ 3 6 / \ 8 5 / 7 Level l = -1
출력
Yes
레벨 -1의 노드는 3 -> 7이며 정렬된 순서를 형성합니다.
입력
2 / \ 3 7 \ / 4 5 Level l = 0
출력
Yes
값이 4와 5인 노드는 이진 트리에서 겹칩니다.
이제 이것이 정렬된 시퀀스 수준을 형성하는지 확인합니다. 레벨 0의 노드는 2 -> 4 -> 5로 정렬된 시퀀스를 형성합니다.
방법
간단한 솔루션에 따르면 먼저 이진 트리의 레벨 순서 순회를 수행하고 각 수직 레벨을 다른 배열에 저장합니다. 이 경우 레벨 l에 해당하는 배열이 정렬되었는지 확인합니다. 이 솔루션에는 줄일 수 있는 큰 메모리 요구 사항이 있습니다.
효율적인 솔루션에 따르면 이진 트리의 수직 수준 순서 탐색을 수행하고 이진 트리의 수직 수준 l에서 노드 값의 추적을 유지합니다. 이전 요소가 현재 요소보다 작거나 같으면 정렬된 시퀀스가 생성됩니다. 수직 레벨 순서 순회를 수행할 때 이전 값을 저장하고 수직 레벨 l의 현재 노드를 레벨 l의 이전 값과 비교합니다. 현재 노드 값이 이전 값보다 크거나 같으면 레벨 l이 끝날 때까지 동일한 절차를 반복해야 합니다. 어떤 단계에서 현재 노드 값이 이전 값보다 작으면 레벨 l이 정렬되지 않는 것으로 나타났습니다. 다시 레벨 l의 끝에 도달하면 레벨이 정렬된다는 것이 관찰되었습니다.
예시
// 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;
} 출력
Yes