如何检查一棵树是否是另一棵树的子树？
因此，我有一个显而易见的蛮力算法，它的运行方式如下
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}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
复制相似问题
腾讯云开发者
