資料結構
網路
關係資料庫管理系統
作業系統
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 次檢視
