如何检查一棵树是否是另一棵树的子树？
因此，我有一个显而易见的蛮力算法，它的运行方式如下
int isSubtree (binTree *S, binTree *T)
{
if (S == NULL)
return 0;
return (isEqual (S,T) || isSubtree (S->left, T) || isSubtree (S->right, T));
}
int isEqual (binTree *S, bintree *T)
{
if (S==NULL && T==NULL)
return 1;
if (S==NULL || T==NULL)
return 0;
if (S->val == T->val)
return isEqual(S->left,T->left) && isEqual (S->right,T->right);
else
return 0;
}但这是O(n²)方法。
我有另一种方法，如下所示，是O(n) We，按顺序遍历第一棵树，并将其存储在一个数组中。然后我们遍历第二棵树，并按顺序存储它。现在，如果第二个数组是第一个数组的子数组，我们继续并对预序遍历重复相同的过程。如果两个查询结果都为真，则该树是第一个树的子树。否则，就不会了。
谁能告诉我下面的算法是否有效？
对于这个问题，有没有更优化的空间解决方案？
注意:我需要两个数组，因为我存储了这两个数组的遍历，有没有只用一个数组就行了？就像我会存储其中一棵树的顺序遍历，然后在遍历另一棵树时使用该数组来检查子数组条件。或者不需要额外的空间，而是O(n)时间复杂度？
注意:通过子数组，我的意思是元素应该连续出现，即
{2,3,5} is a subarray of {1,2,3,5} but not a subarray of {1,2,3,4,5}回答 4
Stack Overflow用户
发布于 2013-07-22 13:16:43
摘要:考虑在每个节点中存储散列和/或子树大小，以加快搜索速度。你提出的算法失败了。
你提出的算法-坏了？
如果我正确理解了你提出的替代算法，那么它就不起作用了。作为一个反例，请考虑：
T S
x x
/ \ / \
y z y z
\
qT有中序遍历yxz，前序xyz。S有中序遍历yxzq，前序xyzq。
因此，T的遍历被嵌入在S中，尽管T不是有效的匹配(根据您的递归方法)。
在递归匹配过程中快速消除子树
我一直在考虑Karthikeyan的建议-在每个节点存储子树深度，因为它可以消除许多比较。当然，如果动态维护，它也会使某些树操作变得更昂贵--在子树查找过程中必须优先考虑这些操作或额外的命中。
存储子树元素的散列是另一种可能性。什么是有意义的取决于与子树查找相比，树的结构和数据是如何动态更新的，以及从整体性能的角度来看，两者中的哪一个更重要。
进一步阅读
无论如何，关于这一点有很多现有的问题，例如Find whether a tree is a subtree of other。哦-也找到了这个- Determine if a binary tree is subtree of another binary tree using pre-order and in-order strings -它似乎支持我上面的逻辑，因为你说递归方法是正确的，但速度很慢。
Stack Overflow用户
发布于 2013-07-22 12:52:31
做一个深度优先搜索并存储每个节点上的子树节点的数量，然后只比较节点数与所讨论的另一棵树相同的父节点的子树，怎么样？
Stack Overflow用户
发布于 2013-12-28 12:37:17
我们可以使用中序遍历和DFS(在二叉树中，它简化为预序遍历)。现在，首先使用DFS，修改两个树的数据结构，并在每个节点上存储其下的子树的编号。之后，编写两个树的顺序遍历，然后使用KMP匹配字符串。在O(n+m) (两个树中的n&m个节点)中，我们可以找到不同的匹配。我们可以使用散列来连接到带有DFS的修改后的图。在与KMP的每次匹配中，我们可以比较两者的DFS修改图(在no.如果它在整个序列中都匹配得很好，那么它就是一个子树，否则我们就去寻找另一个KMP匹配，依此类推。
在上面的示例中，DFS之后'T‘的修改后的数据结构是x(2);y(0);z(0) & for 'S’x(3);y(0);z(1);q(0)。为了'T'：yxz为了'S'：yxzq
我们得到匹配的'yxz‘。现在我们转到DFS modified结构。X处存在不匹配；因此，“T”不是“S”的子树。
https://stackoverflow.com/questions/17779962
复制相似问题
腾讯云开发者
