c++ - 如何检查一棵树是否是另一棵树的子树？

Question

所以，我有明显的暴力算法，如下所示

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}

Answer 1

总结:考虑在每个节点中存储哈希和/或子树大小以加快搜索速度。您提出的算法已损坏。

你提出的算法 - 坏了？

如果我正确理解了您提出的替代算法，那么它是行不通的。作为反例，请考虑:

  T          S
  x          x
 / \        / \
y   z      y   z
                \
                 q

T 有中序遍历 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 - 这似乎支持我上面的逻辑，因为你说递归方法是正确的但速度很慢。