极客笔记C++ 判断节点X是否在节点Y的子树中或者反过来，用于Q个查询
对于Q个查询，可以执行以下操作以查看节点X是否在节点Y的子树中或者反过来：从节点Y开始，遍历其子树并查找节点X。如果找到节点X，则X在Y的子树中。从节点X开始，遍历其子树以查找节点Y来处理反向场景。如果找到节点Y，则Y是X的子树成员。要高效地执行这些测试，可以使用树遍历算法，如深度优先搜索（DFS）或广度优先搜索（BFS）。该方法可以保证准确地确定每个查询中节点之间的关系。
使用的方法
- 原生的深度优先搜索遍历
- 使用哈希集合
原生的深度优先搜索遍历
原生的深度优先搜索遍历方法从节点Y的子树开始执行深度优先搜索遍历，以确定节点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
创建一个包含以Y为根的子树中每个节点的HashSet，以便在Q个查询中使用HashSet。遍历以X为根的子树后，检查每个节点是否存在于HashSet中。假设如果在HashSet中找到了X的子树中的任何节点，则认为X位于Y的子树中。以类似的方式创建以X为根的子树的HashSet，然后确定Y的子树中是否存在于其中的任何节点。与为每个查询重复遍历相比，该技术显著降低了时间复杂度，因此在处理庞大的树和多次搜索时更具优势。通过有效地存储和访问节点，HashSet技术优化了该过程，产生更快和更准确的结果。
步骤
- 创建一个空的HashSet。
-
对从节点Y开始的子树进行深度优先搜索（DFS）遍历。
-
将遍历过程中遇到的每个节点添加到HashSet中。
-
从节点X开始，对其子树进行DFS遍历以执行每个查询。
-
在遍历X的子树时，验证在步骤1中生成的HashSet中的每个节点是否存在。
-
如果在HashSet中找到了X的子树中的任何节点，则认为节点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个查询，可以使用两种技术——Naive DFS遍历和使用HashSet来确定节点X是否存在于节点Y的子树中，反之亦然。在Naive DFS遍历中，使用深度优先搜索（DFS）遍历以节点Y为根的子树，并检查节点X的存在。在反向场景中，它还会从节点X开始进行DFS遍历，以找到节点Y。另一方面，使用HashSet技术通过构建一个包含以Y为根的子树中的每个节点的HashSet来优化节点查找。然后，它为X的子树创建一个HashSet，并确定Y的任何节点是否存在其中。与重复遍历相比，这种方法在时间复杂度上有很大的降低，因此在较大的树和多个查询的情况下，它是首选的选择。这两种方法都能产生准确的结果，并适应不同的树大小和查询数量。根据特定的用例和树特征，选择一个合适的方法可以实现高效而精确的节点关系评估。