数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究使用 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
更新于: 2019-10-22
89 次浏览
广告