数据结构
网络
关系数据库管理系统
操作系统
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 次浏览
