algorithm - 如何使用级别顺序遍历查找两棵树在结构上是否相同？

我提出了一种算法来检查两棵树的结构是否相似，即两棵树中对应节点的数据可能不同，但如果tree1中的节点有一个左子节点，那么tree2中的对应节点也必须有一个左子节点。
算法（node*root1，node*root2）：

    1. Create 2 queues Q1,Q2 and enqueue root1 and root2.
    2. while(Q1 and Q2 are not empty)
         2.a temp1 = deQ(Q1);
         2.b temp2 = deQ(Q2);
           2.c if temp1 has left child then enqueue temp1's left child in Q1
           2.d if temp2 has left child then enqueue temp2's left child in Q2
           2.e if temp1 has right child then enqueue temp1's right child in Q1
           2.f if temp2 has right child then enqueue temp2's right child in Q2
         2.g now check if the size of Q1 and Q2 is equal
         2.h if the size is equal then continue else the two trees are not similar
    3.  End

这个算法正确吗？

最佳答案

目前你的算法本身是行不通的例如，如果tree1根仅具有右子级，tree2仅具有左子级，则您的算法将输出假阳性。
你必须修改算法如下这是一种递归方法，但也有其他可能的方法。

Algorithm(node * root1, node * root2) :

   // if exactly one is NULL and other is not, return false.
   if ( root1 && !root2 ) || ( !root1 && root2 )
       return 0.

   // if both are NULL, return true.
   if ( !root1 && !root2 )
       return 1.

   // Both are valid nodes. So now check there respective child sub-trees.
   return Algorithm( root1->left, root2->left ) && Algorithm( root1->right, root2->right )

你的算法：

    Algorithm(node * root1, node * root2) :
        1. Create 2 queues Q1,Q2 and enqueue root1 and root2.
        // here you skip the Null check for root1 and root2. Should be added.
        2. while(Q1 is not empty or Q2 is not empty)
             2.a temp1 = deQ(Q1);
             2.b temp2 = deQ(Q2);
   // Now Compare the respective children of temp1 & temp2. If not equal, then return false.
               2.c if temp1 has left child then enqueue temp1's left child in Q1
               2.d if temp2 has left child then enqueue temp2's left child in Q2
               2.e if temp1 has right child then enqueue temp1's right child in Q1
               2.f if temp2 has right child then enqueue temp2's right child in Q2
        3.  return true.