二叉树同构问题

1.静态链表

物理上用数组存储，思想为链表形式

struct TreeNode{
    Element 
    int Left;
    int right;
}

用 -1 表示指向空，数字表示指向的数组下标
image.pngimage.png

在右边无序的数组中， 0，3，4都被使用，因此只有** 1 **没有被指向，判断出1为root

2.同构函数逻辑

  1. 左右都为空树
  2. 一棵树为空
  3. 判断根结点
  4. 树没有左结点，返回判断右结点
  5. a. 左边都不空，判断左边和左边元素、右边和右边的元素

b.可能是左右交换，判断左边和右边，右边和左边。

int Isomorphic(Tree R1, Tree R2)
{
  if ((R1 == Null) && (R2 == Null)) // 左右子树都为空
    return 1;
  if  (((R1==Null)&&(R2!=Null)) || ((R1!=Null)&&(R2==Null))) 
    return  0;  // 其中一颗子树为空
  if  (T1[R1].Element != T2[R2].Element) 
    return  0;  // 空结点为空
  if  ((T1[R1].Left == Null ) && ( T2[R2].Left == Null)) // 根的左右结点没有子树
    return  Isomorphic(T1[R1].Right, T2[R2].Right);
  if (((T1[R1].Left != Null) && (T2[R2].Left!=Null)) &&
      ((T1[T1[R1].Left].Element) == (T2[T2[R2].Left].Element))) // 左右子树不需要转换
  {
    return (Isomorphic(T1[R1].Left, T2[R2].Left) &&
            Isomorphic(T1[R1].Right, T2[R2].Right));
  }
  else { // 左右子树需要转换
    return (Isomorphic(T1[R1].Left, T2[R2].Right) &&
            Isomorphic(T1[R1].Right, T2[R2].Left));
  }
}