二叉树是否包含另一棵树？

Question

好吧,伙计们,我今天在接受采访时被问到这个问题,它是这样的:

"告诉一个二叉树是否包含在另一个二叉树中(包含节点的结构和值)"

我想到了以下方法:

将较大的树展平为:

{{{-}a{-}}b{{-}c{-}}}d{{{-}e{{-}f{-}}}g{{{-}h{-}}i{{-}j{-}}}}

(我确实为此编写了代码,{-}意味着空左或右子树,每个子树都包含在{} paranthesis中)

现在对于较小的子树,我们需要匹配这种模式:

{{.*}e{.*}}g{{{.*}h{.*}}i{{.*}j{.*}}}

其中{.*}表示空子树或非空子树.

当时我想,这将是java中一个简单的正则表达式模式匹配问题,但我是竹子.实际上现在我觉得,我刚刚改变了问题(创造了另一个怪物).

是否有一个简单的正则表达式衬里匹配这些模式？我知道可能有其他方法可以解决这个问题,这可能不是最好的方法.我只是想知道这是否可以解决.

Answer 1

我不确定面试官所说的“包含在另一个二叉树中”到底是什么意思。如果面试官要求一种方法来检查 A 是否是 B 的子树，那么这是一种根本不需要正则表达式的方法：

您想要包含空叶的原因是因为当多个节点具有相同的值时，前序和中序可能不够。这是一个例子：

          A
      A       A
   B     B       C
 C         D       B
D           C       D

您还可以检查一下：

另请阅读此内容以获取有关二叉树的前序和中序遍历的更多信息：

现在，如果他指的不仅仅是子树，那么问题可能会变得更加复杂，具体取决于面试官所说的“部分”的含义。您可以将问题视为子图同构问题（树只是图的子集），这是 NP 完全的。

可能有更好的方法，因为树比图受到更多限制且更简单。