4-11 Isomorphic (10 分)

Two trees, T1 and T2, are isomorphic if T1 can be transformed into T2 by swapping left and right children of (some of the) nodes in T1. For instance, the two trees in Figure 1 are isomorphic because they are the same if the children of A, B, and G, but not the other nodes, are swapped. Give a polynomial time algorithm to decide if two trees are isomorphic.

Figure 1

Format of functions:

int Isomorphic( Tree T1, Tree T2 );

where Tree is defined as the following:

typedef struct TreeNode *Tree;
struct TreeNode {
    ElementType Element;
    Tree  Left;
    Tree  Right;
};

The function is supposed to return 1 if T1 and T2 are indeed isomorphic, or 0 if not.

Sample program of judge:

#include <stdio.h>
#include <stdlib.h>

typedef char ElementType;

typedef struct TreeNode *Tree;
struct TreeNode {
    ElementType Element;
    Tree  Left;
    Tree  Right;
};

Tree BuildTree(); /* details omitted */

int Isomorphic( Tree T1, Tree T2 );

int main()
{
    Tree T1, T2;
    T1 = BuildTree();
    T2 = BuildTree();
    printf(“%d\n”, Isomorphic(T1, T2));
    return 0;
}

/* Your function will be put here */

Sample Output 1 (for the trees shown in Figure 1):

Sample Output 2 (for the trees shown in Figure 2):

Figure2

递归这种思想，很有14

写递归的技巧是管好当下，之后的事抛给递归。具体到这里，不管 N 是多少，当前的选择只有两个：匹配 0 次、匹配 1 次。所以可以这样处理：

空根刚刚好，肯定是对的。

一空一不空，&&或者俩元素不一样肯定不对呀

左左右右配对||，或者左右右左配对上一个就行了

int Isomorphic( Tree T1, Tree T2 ){
    if(T1==NULL&&T2==NULL) return 1;
    else if(T1==NULL||T2==NULL||T1->Element!=T2->Element) return 0;
    return Isomorphic(T1->Left,T2->Left)&&Isomorphic(T1->Right,T2->Right)||(Isomorphic(T1->Right,T2->Left)&&Isomorphic(T1->Left,T2->Right));
}