所以，我有一个明显的暴力算法，如下所示
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）我们，以有序的方式遍历第一棵树，并将其存储在数组中。然后我们遍历第二棵树，并以有序的方式存储它。现在，如果第二个数组是第一个数组的子数组，我们也继续并重复相同的预订单遍历过程。如果两个查询的结果都为TRUE，则该树是第一个树的子树。否则，不会。
有人能告诉我下面的算法是否有效吗？
对于这个问题，有没有一个更为空间优化的解决方案？
注意：我需要两个数组，因为我存储了两个数组的遍历，所以我是否可以只使用一个数组？就像我存储其中一棵树的有序遍历一样，然后在遍历另一棵树时使用该数组检查子数组的条件。或者可能没有额外的空间，但O（n）时间复杂性？
注：对于子数组，我的意思是元素应该连续出现，即
{2,3,5} is a subarray of {1,2,3,5} but not a subarray of {1,2,3,4,5}
摘要：考虑在每个节点中存储哈希和/或子树大小，以加快搜索速度。你提出的算法坏了。
你提出的算法坏了
如果我正确理解了你提出的替代算法，那么它就不起作用了。举个反例，考虑一下：
T S
x x
/ /
y z y z
q
T有序遍历yxz，预序xyz。S有序遍历yxzq，预序xyzq。
因此，尽管T不是一个有效的匹配，但T的遍历被嵌入到了s中（根据递归方法）。
在递归匹配过程中快速消除子树
我一直在按照Karthikeyan的建议思考——在每个节点存储子树深度，因为它可以让你省去很多比较。当然，如果动态维护，它也会使某些树操作变得更加昂贵——必须在子树查找过程中对这些操作或额外命中进行优先级排序。
存储子树元素的散列是另一种可能性。有意义的是，与子树的发现相比，树的结构和数据是如何动态更新的，以及从整体性能的角度来看，两者是否更重要。
进一步阅读
无论如何，关于这一点还有很多现存的问题，例如，找出一棵树是否是另一棵树的子树。Ohhh-也发现了这一点-使用预编序和按序字符串确定一个二叉树是否是另一个二元树的子树-这似乎支持我上面的逻辑，因为你说递归方法是正确的，但速度很慢。
进行深度优先搜索并存储每个节点的子树节点数，然后只比较节点数与另一棵树相等的父树的子树。
我们可以使用有序遍历和DFS（在二叉树中，它简化为预序遍历）。现在，首先使用DFS，修改两个树的数据结构，并在每个节点存储其下的子树数量。之后，为这两个树编写有序遍历，然后用KMP匹配字符串。在O（n+m）（两个树中的n&m-节点）中，我们可以找到不同的匹配。我们可以使用哈希来连接到具有DFS的修改图。在与KMP的每次匹配中，我们可以比较两个（在子树数量上）的DFS修改图，如果它对整个序列也匹配，则它是子树，否则我们进行KMP的另一个匹配，依此类推
在上述示例中，DFS之后的修改后的数据结构fot‘T’是[x（2）；y（0）；z（0）]&对于"S"[x（3）；y（0）；z（1）；q（0）]。"T"的订单：yxz订购"S"：yxzq
我们得到了匹配'yxz'。现在我们转到DFS修改的结构。x处存在不匹配；因此，"T"不是"S"的子树。
在数组{2,3,5}中，根可以是2、3或5，因此不能使用这样的数组来表示树。
如果A是B的子树（类似于您的代码），并且假设leafs(x)是从左到右的"树x的叶节点"的数组，则叶（A）是叶（B）的子串。
一旦找到如上所述的子字符串，请检查从叶子到根的节点，以确保它真的是子树。