判断两个二叉树是否相似（结构相同）¶

代码实现¶

C
// 函数 func：判断两个二叉树是否相似（结构相同）
// 参数：T1 - 第一个二叉树的根节点，T2 - 第二个二叉树的根节点
// 返回值：1表示相似，0表示不相似
int func(BiTree T1, BiTree T2) {
    // 情况1：两个节点都为空，结构相同
    if (T1 == NULL && T2 == NULL) {
        return 1;
    }

    // 情况2：其中一个节点为空，另一个不为空，结构不同
    if (T1 == NULL || T2 == NULL) {
        return 0;
    }

    // 递归比较左子树是否相似
    int left = func(T1->lchild, T2->lchild);

    // 递归比较右子树是否相似
    int right = func(T1->rchild, T2->rchild);

    // 只有当左右子树都相似时，整棵树才相似
    return left && right;
}

代码逻辑解析¶

1. 基本概念¶

树相似：两个二叉树具有相同的结构形态，即对应节点的子树分布相同
树相等：两个二叉树不仅结构相同，而且对应节点的数据也相同

2. 算法思路¶

采用递归分治的思想： - 比较当前节点的结构关系 - 递归比较左右子树 - 综合左右子树的结果得出最终结论

3. 递归终止条件¶

C
// 基础情况判断
if (T1 == NULL && T2 == NULL)    // 两个空节点 → 相似
    return 1;
if (T1 == NULL || T2 == NULL)    // 一个空一个非空 → 不相似
    return 0;

4. 递归分解¶

分解：将问题分解为比较左子树和右子树
解决：递归调用函数比较子树
合并：通过逻辑与操作合并子问题结果

时间复杂度分析¶

1. 节点访问次数¶

在最坏情况下，需要访问两个树中的所有节点
设第一个树有 m 个节点，第二个树有 n 个节点
总访问次数为 min(m, n)（因为一旦发现不匹配就提前终止）

2. 每次操作复杂度¶

节点比较操作：O(1)
递归调用开销：O(1)

3. 总体时间复杂度¶

O(min(m, n))，在最坏情况下为 O(n)（假设两树节点数相近）

空间复杂度分析¶

1. 额外空间使用¶

只使用了常量级别的局部变量（left, right）
没有使用额外的数据结构

2. 递归调用栈空间¶

递归深度取决于树的高度
最好情况（平衡二叉树）：O(log n)
最坏情况（退化为链表）：O(n)

3. 总体空间复杂度¶

O(h)，其中 h 是树的高度，在最坏情况下为 O(n)

较难理解部分的说明¶

1. 相似与相等的区别¶

C
// 树相似的例子：
//     T1:     T2:
//      A       X
//     / \     / \
//    B   C   Y   Z
//   /       /
//  D       W
// 结构相同，但节点数据可以不同 → 相似

// 树相等的例子：
//     T1:     T2:
//      A       A
//     / \     / \
//    B   C   B   C
//   /       /
//  D       D
// 结构和数据都相同 → 相等

2. 逻辑与操作的短路特性¶

C
return left && right;

利用逻辑与的短路特性： - 如果 left 为 0（假），不会计算 right，直接返回 0 - 这提供了早期终止优化，提高效率

3. 图解说明¶

假设两棵树：

Text Only
1 2 3 4 5 6	`T1: T2: A X / \ / \ B C Y Z / / \ / / \ D E F W U V`

递归比较过程：

Text Only

func(A,X) → 比较数据（可选）→ func(B,Y) && func(C,Z)
  ↓
func(B,Y) → 比较数据（可选）→ func(D,W) && func(NULL,NULL)
  ↓
func(D,W) → 比较数据（可选）→ func(NULL,NULL) && func(NULL,NULL) → 1&&1=1
  ↓
func(NULL,NULL) → 1
  ↓
func(C,Z) → 比较数据（可选）→ func(E,U) && func(F,V)
  ↓
... 继续递归比较

延伸知识点¶

1. 只判断结构相似的版本¶

C
// 仅判断结构相似，忽略节点数据
int isSimilarStructure(BiTree T1, BiTree T2) {
    if (T1 == NULL && T2 == NULL) {
        return 1; // 两个空树结构相同
    }
    if (T1 == NULL || T2 == NULL) {
        return 0; // 一个空一个非空，结构不同
    }

    // 只比较结构，不比较数据
    return isSimilarStructure(T1->lchild, T2->lchild) &&
           isSimilarStructure(T1->rchild, T2->rchild);
}

2. 非递归版本 - 使用栈¶

C
int isSimilarIterative(BiTree T1, BiTree T2) {
    Stack* stack1 = createStack();
    Stack* stack2 = createStack();

    push(stack1, T1);
    push(stack2, T2);

    while (!isEmpty(stack1) && !isEmpty(stack2)) {
        BiTree node1 = pop(stack1);
        BiTree node2 = pop(stack2);

        // 检查结构一致性
        if ((node1 == NULL) != (node2 == NULL)) {
            return 0; // 一个空一个非空
        }

        if (node1 != NULL && node2 != NULL) {
            // 将子节点入栈
            push(stack1, node1->lchild);
            push(stack1, node1->rchild);
            push(stack2, node2->lchild);
            push(stack2, node2->rchild);
        }
    }

    return isEmpty(stack1) && isEmpty(stack2);
}

3. 扩展应用 - 判断同构¶

C
// 判断两个树是否同构（可以通过交换左右子树变得相同）
int isIsomorphic(BiTree T1, BiTree T2) {
    if (T1 == NULL && T2 == NULL) {
        return 1;
    }
    if (T1 == NULL || T2 == NULL) {
        return 0;
    }

    if (T1->data != T2->data) {
        return 0;
    }

    // 两种情况：不交换子树 或 交换子树
    return (isIsomorphic(T1->lchild, T2->lchild) && 
            isIsomorphic(T1->rchild, T2->rchild)) ||
           (isIsomorphic(T1->lchild, T2->rchild) && 
            isIsomorphic(T1->rchild, T2->lchild));
}

4. 相关算法问题¶

子树判断：¶

C
// 判断 T2 是否是 T1 的子树
int isSubtree(BiTree T1, BiTree T2) {
    if (T2 == NULL) return 1; // 空树是任何树的子树
    if (T1 == NULL) return 0; // 空树不能包含非空树

    // 在当前节点匹配 或 在左子树中匹配 或 在右子树中匹配
    return isSameTree(T1, T2) || 
           isSubtree(T1->lchild, T2) || 
           isSubtree(T1->rchild, T2);
}

树的镜像判断：¶

C
// 判断两个树是否互为镜像
int isMirror(BiTree T1, BiTree T2) {
    if (T1 == NULL && T2 == NULL) {
        return 1;
    }
    if (T1 == NULL || T2 == NULL) {
        return 0;
    }

    return (T1->data == T2->data) &&
           isMirror(T1->lchild, T2->rchild) &&
           isMirror(T1->rchild, T2->lchild);
}

5. 实际应用场景¶

编译器优化：判断表达式树的结构相似性
模式识别：识别具有相同结构的决策树
数据库索引：比较 B+ 树的结构
生物信息学：比较进化树的拓扑结构
图形用户界面：比较 UI 组件树的布局结构

6. 性能优化技巧¶

C
// 带剪枝优化的版本
int isSimilarOptimized(BiTree T1, BiTree T2) {
    // 提前计算节点数进行快速判断（如果可以获取）
    // if (getNodeCount(T1) != getNodeCount(T2)) return 0;

    if (T1 == NULL && T2 == NULL) {
        return 1;
    }
    if (T1 == NULL || T2 == NULL) {
        return 0;
    }

    // 可以添加节点数据的快速比较
    // if (T1->data != T2->data) return 0;

    // 先比较一个子树，如果失败则不必比较另一个
    if (!isSimilarOptimized(T1->lchild, T2->lchild)) {
        return 0;
    }

    return isSimilarOptimized(T1->rchild, T2->rchild);
}

这个算法体现了递归分治的经典思想，通过将复杂问题分解为更小的子问题来解决，是树算法中的基础而重要的问题。