java - 在二叉树中寻找同构性质的算法

Question

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

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; 
}

Answer 1

wikipedia article for 'isomorphism'说“如果两个对象是同构的，那么同构保留的任何属性，并且对其中一个对象为真，对另一个对象也为真。”

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

如果您关心用于搜索的二叉树的行为，则您的算法不正确。参见 What does it mean for two binary trees to be isomorphic?

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

另一方面，如果您关心形状 和 数据，@amits 修复将为您解决。但请注意，您也可以将其称为完全匹配。

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