数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究检查给定的排列是否为给定树的有效BFS
在这个问题中，我们将检查是否可以使用给定的二叉树的 BFS（广度优先搜索）遍历来获得给定数组中 1 到 N 个元素的排列。
在这里，我们将遍历树并使用 BFS 遍历找到所有可能的排列。之后，我们可以检查任何 BFS 遍历结果是否与数组排列匹配。
问题陈述 - 我们给定一个大小为 N 的数组，其中包含前 N 个正整数的随机顺序。此外，我们给定一棵包含前 N 个数字作为树节点的树。我们需要检查是否可以通过树的 BFS 遍历以相同的顺序获得数组元素。
示例
输入
permutation = {1, 3, 2, 6, 4, 5, 8, 7};
1
/ \
2 3
/ \ /
4 5 6
/ \
7 8
输出
Yes
解释 - 使用 BFS 遍历，我们可以遍历二叉树的右子节点或左子节点。在第二层，我们可以先遍历右节点，然后遍历第二个节点。此外，在最后一层，我们先遍历右节点，然后遍历左节点。
输入
permutation = {1, 5, 2, 6, 4, 3, 8, 7};
1
/ \
2 3
/ \ /
4 5 6
/ \
7 8
输出
No
解释 - 二叉树的第二层不包含 5。因此，无法使用 BFS 遍历获得给定的排列。
输入
permutation = {1, 4, 3, 2}
1
/
4
/ \
2 3
输出
Yes
解释 - 给定二叉树的所有 BFS 排列如下所示，给定数组是其中之一。
[1, 4, 2, 3]
[1, 4, 3, 2]
方法
在这种方法中，我们将使用二维数组来创建二叉树。此外，我们将使用无序集合和队列数据结构来解决问题。
这里，解决问题的核心逻辑是将每一层的节点存储在集合中，并创建这样一个集合的队列。因此，我们可以从集合中获取节点并遍历其子节点。对于每个节点，我们可以先遍历右节点或先遍历左节点。
算法
步骤 1 - 创建一个大小为 N + 1 的向量列表。此外，插入元素以创建二叉树。
步骤 2 - 如果 bin_tree[permutation[0]].size() 为 0，则返回 false，因为排列的第一个元素不存在于数组中。
步骤 3 - 定义名为“vis”的无序集合以存储已访问的元素，以及名为“level_nodes”的集合以存储当前节点的元素。此外，定义队列以存储每一层的无序集合。
步骤 4 - 将数组的第一个元素插入到 level_nodes 集合中，并将集合插入到队列中。
步骤 5 - 使用 while 循环进行迭代，直到队列不为空且数组索引小于数组长度。
步骤 6 - 如果当前数组元素存在于“vis”集合中，则返回 false，因为该元素已被访问。
步骤 7 - 将当前数组元素插入到“vis”节点中。
步骤 8 - 如果队列中的第一个集合为空，则将其移除。
步骤 9 - 从队列中获取第一个集合到 level_nodes。
步骤 10 - 如果 level_nodes 不包含当前数组元素，则返回 false。
步骤 11 - 使用 clear() 方法清除 level_nodes 集合。
步骤 12 - 遍历二叉树中与当前元素连接的所有节点。
步骤 12.1 - 如果当前节点未被访问，则将其插入到 level_nodes 集合中。
步骤 13 - 如果 level_nodes 不为空，则将其插入到队列中。
步骤 14 - 从队列的第一个集合中移除当前数组元素。
步骤 15 - 在完成 while 循环的所有迭代后返回 true。
示例
#include <bits/stdc++.h>
using namespace std;
bool checkForValidPerm(vector<int> &permutation, vector<int> *bin_tree) {
// When the first element is not present in the tree
if (bin_tree[permutation[0]].size() == 0) {
return false;
}
// Total nodes in permutation
int len = permutation.size();
unordered_set<int> vis;
// To store nodes of the current level
unordered_set<int> level_nodes;
level_nodes.insert(permutation[0]);
// For BFS traversal
queue<unordered_set<int>> que;
que.push(level_nodes);
int p = 0;
while (!que.empty() && p < len) {
// If the node is already visited
if (vis.count(permutation[p])) {
return false;
}
vis.insert(permutation[p]);
// When all nodes of the first node are visited
if (que.front().empty()) {
que.pop();
}
// When an element is not found
level_nodes = que.front();
if (level_nodes.count(permutation[p]) == 0) {
return false;
}
level_nodes.clear();
// Push all child node to level_nodes
for (int &q : bin_tree[permutation[p]]) {
if (!vis.count(q)) {
level_nodes.insert(q);
}
}
if (!level_nodes.empty()) {
// Insert level_nodes to queue
que.push(level_nodes);
}
// Remove the current node
que.front().erase(permutation[p]);
p++;
}
return true;
}
int main() {
int n = 8;
// Given tree
vector<int> bin_tree[n + 1];
bin_tree[1].push_back(2);
bin_tree[1].push_back(3);
bin_tree[2].push_back(4);
bin_tree[2].push_back(5);
bin_tree[3].push_back(6);
bin_tree[4].push_back(7);
bin_tree[4].push_back(8);
vector<int> permutation = {1, 3, 2, 6, 4, 5, 8, 7};
if (checkForValidPerm(permutation, bin_tree)) {
cout << "Yes, the given permutation is valid BFS traversal." << endl;
} else {
cout << "No, the given permutation is not a valid BFS traversal." << endl;
}
return 0;
}
输出
Yes, the given permutation is valid BFS traversal.
时间复杂度 - O(N*logN)，其中 N 是数组元素的数量。
空间复杂度 - O(N) 用于将树元素存储在集合和队列中。
在这个问题中，我们使用了 BFS 遍历的层次遍历。在遍历每一层时，我们选择访问左子节点或右子节点。程序员可以使用递归函数来查找 BFS 遍历的所有排列。
196 次查看
