我想知道二叉树T2是否是二叉树T1的子树.我读到可以使用预订和有序遍历为T2和T1构建字符串表示,如果T2字符串是T1字符串的子字符串,则T2是T1的子树.
我对这种方法有点困惑,不确定它的正确性.
来自wiki:"树的子树T是由T中的节点及其T中的所有后代组成的树."
在以下示例中:
T2:
1
/ \
2 3
T1:
1
/ \
2 3
\
4
如果我们为T2和T1构建字符串:
预购T2:"1,2,3"
预购T1:"1,2,3,4"
in T2:"2,1,3
"in T1:"2,1,3,4"
T2字符串是T1的子字符串,因此使用上述子字符串匹配方法,我们应该得出结论T2是T1的子树.
但是,根据定义,T2不应该是T1的子树,因为它没有T1的根节点的所有后代.
有一个相关的讨论在这里,这似乎结束方法是正确的.
我在这里错过了什么吗？
好吧,伙计们,我今天在接受采访时被问到这个问题,它是这样的:
"告诉一个二叉树是否包含在另一个二叉树中(包含节点的结构和值)"
我想到了以下方法:
将较大的树展平为:
{{{-}a{-}}b{{-}c{-}}}d{{{-}e{{-}f{-}}}g{{{-}h{-}}i{{-}j{-}}}}
(我确实为此编写了代码,{-}意味着空左或右子树,每个子树都包含在{} paranthesis中)
现在对于较小的子树,我们需要匹配这种模式:
{{.*}e{.*}}g{{{.*}h{.*}}i{{.*}j{.*}}}
其中{.*}表示空子树或非空子树.
当时我想,这将是java中一个简单的正则表达式模式匹配问题,但我是竹子.实际上现在我觉得,我刚刚改变了问题(创造了另一个怪物).
是否有一个简单的正则表达式衬里匹配这些模式？我知道可能有其他方法可以解决这个问题,这可能不是最好的方法.我只是想知道这是否可以解决.