資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究查詢節點 X 是否存在於另一個節點 Y 的子樹中，反之亦然（針對 Q 次查詢）
對於 Q 次查詢，請執行以下操作以檢視節點 X 是否在節點 Y 的子樹中或反之亦然：從節點 Y 開始，遍歷其子樹，同時注意節點 X。如果發現，則 X 在 Y 的子樹中。在反向場景中，從節點 X 開始並遍歷其子樹以查詢節點 Y。如果找到 Y，則 Y 是 X 的子樹的成員。為了有效地執行這些測試，可以使用樹遍歷演算法，例如深度優先搜尋 (DFS) 或廣度優先搜尋 (BFS)。該過程保證了每次查詢中節點之間關係的準確確定。
使用的方法
樸素 DFS 遍歷
使用 HashSet
樸素 DFS 遍歷
樸素 DFS 遍歷方法從節點 Y 的子樹的深度優先搜尋 (DFS) 遍歷開始，以確定節點 X 是否存在於節點 Y 的子樹中，反之亦然（針對 Q 次查詢）。驗證在整個遍歷過程中是否遇到節點 X。如果是，則證明 X 是 Y 的子樹的一部分。在場景相反的情況下，重複此過程，從節點 X 開始 DFS 以查詢節點 Y。由於重複遍歷，這種方法對於大型樹可能變得昂貴，但對於小型樹和少量查詢來說，它簡單有效。
演算法
對於每個查詢，確定將要測試的節點 Y（或在 Y:X 情況下為 X）和節點 X（或在 Y:X 情況下為 Y）。
從以節點 Y 為根的子樹開始，開始深度優先搜尋 (DFS) 探索。
在遍歷時，驗證當前節點和節點 X 是否相等。
如果遇到節點 X，則節點 X 證明 X 存在於 Y 的子樹中。返回 True。
透過針對每個 Q 查詢再次執行該過程來檢查 X 是否存在於 Y 的子樹中。
從以節點 X 為根的子樹開始，反向執行 DFS 遍歷。
在遍歷期間，檢視當前節點是否與節點 Y 匹配。
如果遇到節點 Y，則節點 Y 確認 Y 存在於 X 的子樹中。返回 True。
檢查每個 Q 查詢的結果，以檢視 Y 是否存在於 X 的子樹中。
如果查詢的遍歷已完成但未在子樹中找到節點，則返回 False 以表明節點不存在。
該過程使用 DFS 遍歷快速建立每次查詢中節點 X 和 Y 之間的關係。
示例
#include <iostream>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
bool isNodePresent(TreeNode* root, int target) {
if (root == NULL)
return false;
if (root->val == target)
return true;
return isNodePresent(root->left, target) || isNodePresent(root->right, target);
}
bool isSubtree(TreeNode* Y, TreeNode* X) {
if (Y == NULL)
return false;
if (Y->val == X->val && isNodePresent(Y, X->val))
return true;
return isSubtree(Y->left, X) || isSubtree(Y->right, X);
}
int main() {
TreeNode* rootY = new TreeNode(3);
rootY->left = new TreeNode(4);
rootY->right = new TreeNode(5);
rootY->left->left = new TreeNode(1);
rootY->left->right = new TreeNode(2);
TreeNode* rootX = new TreeNode(4);
rootX->left = new TreeNode(1);
rootX->right = new TreeNode(2);
if (isSubtree(rootY, rootX))
cout << "X is present in the subtree of Y." << endl;
else
cout << "X is not present in the subtree of Y." << endl;
return 0;
}
輸出
X is present in the subtree of Y.
使用 HashSet
為了使用 HashSet 進行 Q 次查詢，建立一個包含以 Y 為根的子樹中的每個節點的 HashSet。在以 X 為根遍歷子樹後，檢查每個節點是否都存在於 HashSet 中。如果發現 X 的子樹中的任何節點都存在於 HashSet 中，則假定 X 位於 Y 的子樹中。以類似的方式為以 X 為根的子樹建立一個 HashSet，然後確定 Y 的子樹中的任何節點是否存在於其中。與針對每個查詢進行重複遍歷相比，這種技術顯著降低了時間複雜度，使其對於大型樹和多次搜尋更有優勢，因為 HashSet 的快速節點查詢優於重複遍歷。透過有效地儲存和訪問節點，HashSet 技術優化了過程，產生了更快、更準確的結果。
演算法
建立一個空的 HashSet。
執行從節點 Y 開始的子樹的深度優先搜尋 (DFS) 遍歷。
將遍歷過程中遇到的每個節點都新增到 HashSet 中。
從節點 X 開始，並針對每個查詢使用 DFS 遍歷其子樹。
在遍歷 X 的子樹時，驗證步驟 1 中生成的 HashSet 中是否存在每個節點。
如果發現 X 的子樹中的任何節點都存在於 HashSet 中，則節點 X 位於節點 Y 的子樹中。
重複步驟 2 到 6，在為 X 的子樹建立 HashSet 後，檢查 Y 的子樹中的任何節點是否存在。
對於每個查詢，該過程有效地建立了節點 X 和 Y 之間的關係。
示例
#include <iostream>
#include <unordered_set>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
void createHashSet(TreeNode* root, unordered_set<int>& nodes) {
if (!root) return;
nodes.insert(root->val);
createHashSet(root->left, nodes);
createHashSet(root->right, nodes);
}
bool isSubtree(TreeNode* Y, TreeNode* X) {
unordered_set<int> YNodes;
createHashSet(Y, YNodes);
unordered_set<int> XNodes;
createHashSet(X, XNodes);
for (const auto& val : YNodes) {
if (XNodes.count(val))
return true;
}
return false;
}
int main() {
TreeNode* rootY = new TreeNode(3);
rootY->left = new TreeNode(4);
rootY->right = new TreeNode(5);
rootY->left->left = new TreeNode(1);
rootY->left->right = new TreeNode(2);
TreeNode* rootX = new TreeNode(4);
rootX->left = new TreeNode(1);
rootX->right = new TreeNode(2);
if (isSubtree(rootY, rootX))
cout << "X is present in the subtree of Y." << endl;
else
cout << "X is not present in the subtree of Y." << endl;
return 0;
}
輸出
X is present in the subtree of Y.
結論
總之，對於 Q 次查詢，可以使用兩種技術——樸素 DFS 遍歷和使用 HashSet——來確定節點 X 是否存在於節點 Y 的子樹中，反之亦然。在樸素 DFS 遍歷中，使用深度優先搜尋 (DFS) 遍歷以節點 Y 為根的子樹，並檢查節點 X 的存在性。在反向場景中，它還從節點 X 執行 DFS 遍歷以查詢節點 Y。另一方面，使用 HashSet 技術透過構建一個包含以 Y 為根的子樹中每個節點的 HashSet 來最佳化節點查詢。然後，它為 X 的子樹建立一個 HashSet，並確定 Y 的任何節點是否存在於其中。與重複遍歷相比，這種方法顯著降低了時間複雜度，這使其成為對於更大的樹和多個查詢的更佳選擇。這兩種方法都產生準確的結果，同時適應不同的樹大小和查詢量。根據特定用例和樹特徵選擇合適的方法可以導致高效且精確的節點關係評估。
87 次瀏覽
