3

检查两个二叉树本质上同构的算法是什么？我的代码-

boolean isIsomorphic(Root t1 , Root t2){
    if(t1==null || t2==null){
        return false;
    }

    if((t1.value == t2.value) && (isIsomorphic(t1.left,t2.right) && isIsomorphic(t1.right,t2.left))) {
        return true
    }

    return false; 
}
4

2 回答 2

3

关于“同构”的维基百科文章说：“如果两个对象是同构的，那么由同构保留的任何属性并且对于其中一个对象是正确的，对另一个对象也是正确的。”

所以你的问题需要说明你是否关心形状、数据、性能等。

如果您关心搜索二叉树的行为，那么您的算法是不正确的。请参阅两个二叉树同构意味着什么？

检查同构的最简单方法是按顺序遍历两棵树，检查每一步之后的值。

另一方面，如果您关心形状和数据，@amits 修复程序将为您解决。但请注意，您不妨称之为完全匹配。

最后，如果您只关心形状，那么您需要放弃检查t1.value == t2.value

于 2012-04-27T15:19:58.293 回答
0

从这里开始：如果 s 可以通过交换 s 的一些节点的左右子节点转换为 t，那么两棵树 s 和 t 是准同构的。节点中的值在确定准同构时并不重要，只有形状很重要。

该链接还提供了此同构定义的代码。

如果这些值很重要，则方法可能如下：

  1. 使用两个队列对每棵树进行逐级遍历
  2. 在两棵树中添加完关卡后，检查队列大小。如果不同，请报告“非同构”
  3. 否则，对于第一棵树，将该级别中的所有节点出列到一个集合中。
  4. 对于第二棵树，将每个节点出列并检查它是否存在于集合中。
  5. 如果集合成员测试失败，报告“NOT ISOMORPHIC”。
  6. 如果我们完成所有级别，请报告 ISOMORPHIC。
于 2013-03-27T23:50:35.463 回答