判断两棵二叉树是否同构，三种实现方式（递归、队列、堆栈）

一、同构的概念：

       给定两棵二叉树 T1 和 T2，如果T2可以通过若干次左右孩子互换就变成T1，那么我们称这两棵树是同构的

例1：下图两棵树同构，因为对T2，交换A左右孩子；交换B左右孩子，交换G左右孩子，经过3次交换后，T2=T1，即两棵树全等，所以说这两棵树是同构的。

例2：下面两棵树异构，因为对T2-B的左右孩子不等于T1-B，所以异构。

二、二叉树的表示：

        数组表示法：一棵结点数为5的二叉树可以表示为下图

        缺点：浪费空间，5个结点就需要13个空间来保存，增删改不方便。

        优点：空间地址连续，能够快速查找

         

        链表表示法：一棵结点数为5的二叉树可以表示为下图

        优点：增删改方便。

        缺点：查找速度慢，空间地址不连续。        

        静态链表表示法：静态链表是物理结构是数组，但是使用了链表的思想的一种抽象数据结构。很好的融合了两者的优点，空间地址连续，查找起来快，且不浪费空间。 

三、递归法，判断二叉树是否同构

分析：两棵二叉树同构的情况有下列几种：

        ① 均为空

        ② 全等

        ③ 交换左右子树后全等

据此，可以用代码实现：

def isomorphic(R1, R2, T1, T2):
    """
    R1: T1 的根节点
    R2：T2 的根节点
    T1：T1树
    T2：T2数
    判断两棵树是否同构
        同构的情况：
        ① 两棵树都为空 (全等)
        ② 两棵树全等
        ③ 左/右结点交换后全等
    """
    # 两棵树都为空
    if R1==NULL and R2==NULL:
        return True

    if R1.element == R2.element:
        if R1.left==NULL and R2.left==NULL:  # 左子树为空，右子树同构
            return isomorphic(R1=T1.get(R1.right), R2=T2.get(R2.right), T1=T1, T2=T2)

        if (R1.left!=NULL and R2.left!=NULL) and \
                (T1.get(R1.left).element == T2.get(R2.left).element):  # 两棵树全等
            return (isomorphic(R1=T1.get(R1.left), R2=T2.get(R2.left), T1=T1, T2=T2) and
                    isomorphic(R1=T1.get(R1.right), R2=T2.get(R2.right), T1=T1, T2=T2))
        else:  # 交换后全等
            return (isomorphic(R1=T1.get(R1.left), R2=T2.get(R2.right), T1=T1, T2=T2) and
                    isomorphic(R1=T1.get(R1.right), R2=T2.get(R2.left), T1=T1, T2=T2))

    return False

四、队列法

分析：我们可以参考层序遍历来做，每个结点都当作一棵树，只要所有结点同构，那么这两棵树就同构。

def isomorphic2(R1, R2, T1, T2):
    """
    R1: T1 的根节点
    R2：T2 的根节点
    T1：T1树
    判断是否同构
    """
    s = QueueArr()
    s.addQ((R1, R2))
    flag = True

    while (not (s.isEmpty())):
        r1, r2 = s.deleteQ()

        if r1==NULL and r2==NULL:
            continue # 空树全等

        if (r1!=NULL and r2!=NULL) and (r1.element == r2.element):

            if r1.left==NULL and r2.left==NULL:  # 左子树为空，右子树同构
                s.addQ((T1.get(r1.right), T2.get(r2.right)))
                continue

            if (r1.left!=NULL and r2.left!=NULL) \
                and (T1.get(r1.left).element == T2.get(r2.left).element):
                s.addQ((T1.get(r1.left), T2.get(r2.left)))
                s.addQ((T1.get(r1.right), T2.get(r2.right)))
                continue
            else:
                s.addQ((T1.get(r1.left), T2.get(r2.right)))
                s.addQ((T1.get(r1.right), T2.get(r2.left)))
                continue

        return False

    return flag

五、堆栈法

分析：

        ① 堆栈法和先序遍历算法差不多，遇到一个结点，先判断当前元素是否相等；

        ② 若不相等，直接抛出异构；若相等，继续判断T1，T2左子树，当T2左子树不等于T1左子树时，交换T2左右子树，并且把此时两个结点压入栈，因为左子树判断完需要回头判断右子树。

        ③ 当遍历完左子树，跳到兄弟右子树，回到步骤1；

        如此循环，直到整棵树遍历完，如果都没有抛出异构，那么这两棵树同构。

def isomorphic3(R1, R2, T1, T2):
    """
    判断是否同构
    """
    s = ArrStack()
    p1 = R1
    p2 = R2

    while ((p1!=NULL and p2!=NULL) or (not (s.isEmpty()))):

        while(p1!=NULL and p2!=NULL):  # 遍历左子树
            if p1.element!= p2.element:  # 判断当前指针所指的元素是否相等
                return False

            s.push((p1, p2))

            if (p1.left==NULL and p2.left==NULL):
                ...
            elif not ((p1.left!=NULL and p2.left!=NULL) and (T1.get(p1.left).element == T2.get(p2.left).element)):
                t = p2.left
                p2.left = p2.right
                p2.right = t

            p1 = T1.get(p1.left)
            p2 = T2.get(p2.left)

        if p1==NULL and p2==NULL:  # 跳到右子树
            p1, p2 = s.pop()
            p1 = T1.get(p1.right)
            p2 = T2.get(p2.right)
        else:
            return False

    return True

六、效率对比

现有T1，T2

分别调用3种算法

 效率对比如下

可以看到堆栈实现速度最快，比递归快7-8倍。