C++에서 바이너리 트리가 레벨별로 정렬되었는지 확인하십시오.

여기에서 이진 트리가 레벨별로 정렬되었는지 여부를 확인하는 방법을 볼 것입니다. 레벨별로 정렬된 이진 트리는 다음과 같습니다. -

각 수준에서 노드는 왼쪽에서 오른쪽으로 정렬되며 각 레이어는 이전 수준보다 높은 값을 포함합니다.

레벨 순서 순회를 수행하여 이 문제를 해결할 수 있고 현재 레벨의 최소 및 최대 요소를 추적할 수 있습니다. 다른 변수 prev_max를 사용하여 이전 수준의 최대값을 유지합니다. 그런 다음 현재 레벨의 최소값과 이전 레벨 prev_max의 최대값을 비교합니다. 최소값이 prev_max보다 크면 트리가 현재 레벨까지 레벨별로 정렬됩니다. 그런 다음 prev_max를 업데이트하고 현재 레벨의 최대값을 업데이트합니다. 모든 레벨이 트래버스되지 않을 때까지 이 작업을 반복합니다.

예시

#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