劍指Offer：判斷樹的子結構（九度OJ 1520）

題目描述

輸入兩棵二叉樹 A、B，判斷 B 是否為 A 的子結構。

輸入格式

• 多測試用例，EOF 結束
• 每用例第一行：n, m（1 ≤ n,m ≤ 1000），樹 A、B 的節點數
• 第二行：n 個整數，樹 A 節點值（編號 1~n）
• 接下來 n 行：每行先給孩子數 K_i，再給 K_i 個孩子編號
• 再給 m+1 行：樹 B 的同樣描述

輸出

YES 或 NO

樣例

輸入：
7 3
8 8 7 9 2 4 7
2 2 3
2 4 5
0
0
2 6 7
0
0
8 9
2 2 3
0
0
1 1
2 0
3 0

輸出：
YES
NO

解題思路

關鍵難點

1. 空樹處理：題目說明 n,m ≥ 1，但測試數據可能包含空樹，需在讀入後判斷 n==0 || m==0
2. 單孩子輸入格式：樣例未給出單孩子情況，但測試數據可能有。單孩子時輸入為：1 孩子編號，約定為左孩子
3. 子結構定義：B 為空樹時不是任何樹的子結構

算法策略

雙重遞歸：

1. testForCompare(t1, node, t2)：在樹 A 中遍歷每個節點，嘗試以該節點為根與樹 B 匹配
2. compare(t1, node1, t2, node2)：判斷以 node1 和 node2 為根的兩棵子樹是否完全相同（值相同且結構相同）

匹配邏輯：

• 若 B 當前節點為 0（已匹配完），返回成功
• 若 A 當前節點為 0 但 B 不為 0，返回失敗
• 值不等，返回失敗
• 遞歸比較左子樹 && 右子樹

完整代碼

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

#define MAXSIZE 1005

typedef struct TreeElement {
    int num;
    int lchild;
    int rchild;
} TreeElement;

typedef struct TreeArr {
    TreeElement arr[MAXSIZE];
} TreeArr;

int testForCompare(TreeArr *t1, int t1_idx, TreeArr *t2);
int compare(TreeArr *t1, int t1_idx, TreeArr *t2, int t2_idx);

int main(void) {
    int n, m, i, nchild, n1, n2;
    TreeArr *t1 = (TreeArr *)malloc(sizeof(TreeArr));
    TreeArr *t2 = (TreeArr *)malloc(sizeof(TreeArr));
    
    while (scanf("%d %d", &n, &m) != EOF) {
        // 初始化
        for (i = 0; i < MAXSIZE; i++) {
            t1->arr[i].num = t1->arr[i].lchild = t1->arr[i].rchild = 0;
            t2->arr[i].num = t2->arr[i].lchild = t2->arr[i].rchild = 0;
        }
        t1->arr[0].num = n;
        t2->arr[0].num = m;
        
        // 讀取樹 A
        for (i = 1; i <= n; i++) scanf("%d", &t1->arr[i].num);
        for (i = 1; i <= n; i++) {
            scanf("%d", &nchild);
            if (nchild == 2) {
                scanf("%d %d", &n1, &n2);
                t1->arr[i].lchild = n1;
                t1->arr[i].rchild = n2;
            } else if (nchild == 1) {
                scanf("%d", &n1);
                t1->arr[i].lchild = n1;  // 約定單孩子為左孩子
            }
        }
        
        // 讀取樹 B
        for (i = 1; i <= m; i++) scanf("%d", &t2->arr[i].num);
        for (i = 1; i <= m; i++) {
            scanf("%d", &nchild);
            if (nchild == 2) {
                scanf("%d %d", &n1, &n2);
                t2->arr[i].lchild = n1;
                t2->arr[i].rchild = n2;
            } else if (nchild == 1) {
                scanf("%d", &n1);
                t2->arr[i].lchild = n1;
            }
        }
        
        // 判斷子結構
        if (testForCompare(t1, 1, t2)) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

int testForCompare(TreeArr *t1, int t1_idx, TreeArr *t2) {
    int result = 0;
    if (t1_idx != 0 && t2->arr[0].num != 0) {
        if (t1->arr[t1_idx].num == t2->arr[1].num)
            result = compare(t1, t1_idx, t2, 1);
        if (!result) result = testForCompare(t1, t1->arr[t1_idx].lchild, t2);
        if (!result) result = testForCompare(t1, t1->arr[t1_idx].rchild, t2);
    }
    return result;
}

int compare(TreeArr *t1, int t1_idx, TreeArr *t2, int t2_idx) {
    if (t2_idx == 0) return 1;      // B 匹配完成
    if (t1_idx == 0) return 0;      // A 結束但 B 未完
    if (t1->arr[t1_idx].num != t2->arr[t2_idx].num) return 0;
    return compare(t1, t1->arr[t1_idx].lchild, t2, t2->arr[t2_idx].lchild) &&
           compare(t1, t1->arr[t1_idx].rchild, t2, t2->arr[t2_idx].rchild);
}

/**************************************************************
 Problem: 1520
 Result: Accepted
 Time: 10 ms
 Memory: 912 kb
 **************************************************************/

複雜度分析

• 時間複雜度：O(n × m)，最壞情況 A 每個節點都嘗試匹配 B
• 空間複雜度：O(h_A + h_B)，遞歸棧深度