c++ - 是否可以检查两个二叉树在线性时间内是否同构？

Question

假设所有节点值都相同。我们想知道两个这样的二叉树是否同构。允许左右翻转 child 。

好的，有人问我做了什么。这里是。我采用了幼稚的方法。

bool isIsomorphic(Node* a, Node* b) {
   if(a == b) return true;
   if(!a || !b) return false;

   return isIsomorphic(a->left, b->left) && isIsomorphic(a->right, b->right)
       || isIsomorphic(a->left, b->right) && isIsomorphic(a->right, b->left);

}

Answer 1

是的。该算法归功于Aho--Hopcroft--Ullman。

逐层处理树自下而上。每个节点都标有一个正整数，该整数介于 1 和其级别上的节点数之间，在其级别内标识其同构类。这两棵树是同构的当且仅当它们以相同的标签结束。

当我们处理一层时，更深一层的节点已经被处理过了。为了计算这个级别的标签，我们从一堆无序对 {L, R} 开始，其中 L 是左 child 的标签，R 是右 child 的标签(0 表示空 child )，我们为每个 child 分配一个正数整数。这是通过对对进行基数排序(一次一个坐标)然后比较排序顺序中相邻的元素来完成的。排序后的标签是非递减的；只要两个连续的对不同，它们就会增加。