二叉树的同构判断

二叉树的同构判断

今天重新理了一下同构的思路：

首先，不多说废话，先上图：

 

        这个题的重点部分就在后面递归的应用写法，我们知道给定两棵树T1和T2。如果T1可以通过若干次左右孩子互换就变成T2，则我们称两棵树是“同构”的。

        那么最后的部分的大框架就是，如果两棵树的左右孩子本身就一样，那么是同构的：即

Isomorphism(T1[R1].Left, T2[R2].Left)&&Isomorphism(T1[R1].right, T2[R2].right) == 1；

           或者（T1的左孩子等于T2的右孩子，T1的右孩子等于T2的左孩子）

Isomorphism(T1[R1].Left, T2[R2].right)&&Isomorphism(T1[R1].right, T2[R2].Left) == 1；

       从这里不难看出，这两者之间是或的关系，即在中间加上 ||判断函数就写完了。

       这道题是采用的数组实现二叉树 ， 相关定义如下：

 

           本题的构造创建二叉树没有特别的地方，主要是作者觉得判断方面可以精简一下，因此写下这篇文章，希望可以帮到有需要的人，共勉。