极客笔记C++ 检查给定排列是否是给定树的有效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。所以，使用广度优先搜索遍历无法得到给定的排列。
输入
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遍历的所有排列。