問(wèn)題描述

給定兩棵樹(shù)T1和T2。如果T1可以通過(guò)若干次左右孩子互換就變成T2，則我們稱兩棵樹(shù)是“同構(gòu)”的。例如圖1給出的兩棵樹(shù)就是同構(gòu)的，因?yàn)槲覀儼哑渲幸豢脴?shù)的結(jié)點(diǎn)A、B、G的左右孩子互換后，就得到另外一棵樹(shù)。而圖2就不是同構(gòu)的。

image.png

圖1

image.png

圖2

現(xiàn)給定兩棵樹(shù)，請(qǐng)你判斷它們是否是同構(gòu)的。

輸入格式:

輸入給出2棵二叉樹(shù)樹(shù)的信息。對(duì)于每棵樹(shù)，首先在一行中給出一個(gè)非負(fù)整數(shù)N (≤10)，即該樹(shù)的結(jié)點(diǎn)數(shù)（此時(shí)假設(shè)結(jié)點(diǎn)從0到N?1編號(hào)）；隨后N行，第i行對(duì)應(yīng)編號(hào)第i個(gè)結(jié)點(diǎn)，給出該結(jié)點(diǎn)中存儲(chǔ)的1個(gè)英文大寫(xiě)字母、其左孩子結(jié)點(diǎn)的編號(hào)、右孩子結(jié)點(diǎn)的編號(hào)。如果孩子結(jié)點(diǎn)為空，則在相應(yīng)位置上給出“-”。給出的數(shù)據(jù)間用一個(gè)空格分隔。注意：題目保證每個(gè)結(jié)點(diǎn)中存儲(chǔ)的字母是不同的。

輸出格式:

如果兩棵樹(shù)是同構(gòu)的，輸出“Yes”，否則輸出“No”。

輸入樣例1（對(duì)應(yīng)圖1）：

8
A 1 2
B 3 4
C 5 -
D - -
E 6 -
G 7 -
F - -
H - -
8
G - 4
B 7 6
F - -
A 5 1
H - -
C 0 -
D - -
E 2 -

輸出樣例1:

Yes

輸入樣例2（對(duì)應(yīng)圖2）：

8
B 5 7
F - -
A 0 3
C 6 -
H - -
D - -
G 4 -
E 1 -
8
D 6 -
B 5 -
E - -
H - -
C 0 2
G - 3
F - -
A 1 4

輸出樣例2:

No

解決思路

分別找到兩棵樹(shù)的根
利用層序遍歷即可得出答案，我們遍歷得出同樣的順序即表明是同構(gòu)的樹(shù)
根據(jù)題意的同構(gòu)，在左右節(jié)點(diǎn)相反時(shí)，互換左右節(jié)點(diǎn)push順序
我們只需修改List Leaves中的一些函數(shù)即可

Some Detail Of Function

int printResult(Pnode p, Pnode p1, int root, int root1)：需要提及一點(diǎn)，一開(kāi)始需要判斷兩個(gè)根是否一致，才能往下比較

Notice：注意空樹(shù)的特殊情況！

Code

#include<stdio.h>
#include<malloc.h>
#define SIZE 15
typedef struct node {
    int left;
    int right;
    int isRoot;
    char symbol;
}Node, *Pnode;
typedef struct queue
{
    Pnode queue[SIZE + 1];
    int front;
    int rear;
}Queue, *Pqueue;
Pqueue createQueue(void);
Pnode createList(int length);
int findRoot(Pnode node, int lenght);
int printResult(Pnode p, Pnode p1, int root, int root1);
int getValue(void);
Pnode pop(Pqueue queue);
void push(Pqueue p, Pnode node);
int isEmpty(Pqueue p);
int main(void) {
    int length;
    int length1;
    int root;
    int root1;
    scanf("%d", &length);
    Pnode array = createList(length);
    scanf("%d", &length1);
    Pnode array1 = createList(length1);
    if (length != length1) {
        printf("No");
        return 0;
    }
    else if (length == 0) {
        printf("Yes");
        return 0;
    }
    root = findRoot(array, length);
    root1 = findRoot(array1, length1);
    if (printResult(array, array1, root, root1))
        printf("Yes");
    else
        printf("No");
    return 0;
}
Pnode createList(int length) {
    Pnode array = (Pnode)malloc(sizeof(Node)*length);
    char right;
    char left;
    getchar();
    for (int i = 0; i < length; i++) {
        scanf("%c ", &array[i].symbol);
        array[i].isRoot = 1;
        array[i].left = getValue();
        array[i].right = getValue();
    }
    return array;
}
Pqueue createQueue(void) {
    Pqueue p = 0;
    p = (Pqueue)malloc(sizeof(Queue));
    p->front = p->rear = 0;
    return p;
}
int findRoot(Pnode node, int lenght) {
    for (int i = 0; i < lenght; i++) {
        if (node[i].left != -1)
            node[node[i].left].isRoot = 0;
        if (node[i].right != -1)
            node[node[i].right].isRoot = 0;
    }
    for (int j = 0; j < lenght; j++) {
        if (node[j].isRoot == 1)
            return j;
    }
    return 0;
}
Pnode pop(Pqueue queue) {
    Pnode p = queue->queue[queue->rear++];
    return p;
}
int getValue(void) {
    int count = 0;
    char value;
    char temp[5];
    for (; (value = getchar()) != ' ' && value != '\n';) {
        temp[count++] = value;
    }
    if (count == 2) {
        return 10;
    }
    else if (temp[0] == '-') {
        return -1;
    }
    else {
        return temp[0] - '0';
    }
}
int isEmpty(Pqueue p) {
    if (p->front == p->rear)
        return 1;
    return 0;
}
void push(Pqueue p, Pnode node) {
        p->queue[p->front++] = node;
}
int printResult(Pnode p, Pnode p1, int root, int root1) {
    Pqueue queue = createQueue();
    Pqueue queue1 = createQueue();
    Pnode check;
    Pnode check1;
    if (p[root].symbol != p1[root1].symbol) {
        return 0;
    }
    push(queue, &p[root]);
    push(queue1, &p1[root1]);
    for (; !isEmpty(queue);) {
        check = pop(queue);
        check1 = pop(queue1);
        if (p[check->left].symbol == p1[check1->left].symbol && p[check->right].symbol == p1[check1->right].symbol) {
            if (check->left != -1) {
                push(queue, &p[check->left]);
                push(queue1, &p1[check1->left]);
            }
            if (check->right != -1) {
                push(queue, &p[check->right]);
                push(queue1, &p1[check1->right]);
            }
            
        }
        else if (p[check->left].symbol == p1[check1->right].symbol && p[check->right].symbol == p1[check1->left].symbol) {
            if (check->left != -1) {
                push(queue, &p[check->left]);
                push(queue1, &p1[check1->right]);
            }
            if (check->right != -1) {
                push(queue, &p[check->right]);
                push(queue1, &p1[check1->left]);
            }
        }
        else {
            return 0;
        }
    }
    return 1;
}

Summary

這題總體較為簡(jiǎn)單，明白層序遍歷便可以輕松答出，唯一需要注意的便是在copy一些重復(fù)代碼時(shí)，記得要修改?。?！