EB7-二叉树左右子树交换¶

代码实现¶

C
/**
 * 交换二叉树中所有结点的左右子树（修正版）
 * @param p 当前处理的二叉树结点
 */
void swapSubtrees(BiTree p) {
    // 如果当前结点不为空，则继续处理
    if (p != NULL) {
        // 交换当前结点的左右子树
        BiTree temp = p->lchild;      // 临时保存左子树
        p->lchild = p->rchild;        // 左子树指向右子树
        p->rchild = temp;             // 右子树指向原左子树

        // 递归交换左子树中的所有结点的左右子树
        swapSubtrees(p->lchild);

        // 递归交换右子树中的所有结点的左右子树
        swapSubtrees(p->rchild);
    }
}

代码执行流程图解¶

Text Only

交换前的二叉树：
       A
      / \
     B   C
    / \   \
   D   E   F
  /       / \
 G       H   I

交换过程：
1. 处理根节点A：交换B和C
       A
      / \
     C   B
    /   / \
   F   D   E
      /   /
     G   H
          \
           I

2. 处理C结点：交换F的左右子树（F为叶子结点，无变化）
3. 处理B结点：交换D和E
4. 处理F结点：交换H和I
5. 处理D结点：交换G的左右子树（G为叶子结点，无变化）
6. 处理E结点：交换其子树（E无右子树，相当于将H移到左边）

最终结果：
       A
      / \
     C   B
    /   / \
   F   E   D
  / \     /
 I   H   G

优化版本：更清晰的实现¶

C
/**
 * 交换二叉树中所有结点的左右子树（优化版）
 * @param p 当前处理的二叉树结点
 */
void swapSubtreesOptimized(BiTree p) {
    // 递归终止条件：空结点
    if (p == NULL) {
        return;
    }

    // 交换当前结点的左右子树（使用C语言的逗号表达式技巧）
    BiTree temp = p->lchild;
    p->lchild = p->rchild;
    p->rchild = temp;

    // 递归处理左右子树
    swapSubtreesOptimized(p->lchild);
    swapSubtreesOptimized(p->rchild);
}

另一种实现方式：后序遍历¶

C
/**
 * 使用后序遍历方式交换二叉树左右子树
 * 先交换子树，再交换当前结点
 * @param p 当前处理的二叉树结点
 */
void swapSubtreesPostorder(BiTree p) {
    if (p == NULL) {
        return;
    }

    // 先递归处理左右子树
    swapSubtreesPostorder(p->lchild);
    swapSubtreesPostorder(p->rchild);

    // 再交换当前结点的左右子树
    BiTree temp = p->lchild;
    p->lchild = p->rchild;
    p->rchild = temp;
}

复杂度分析¶

时间复杂度：O(N)¶

分析过程：
函数需要访问二叉树的每一个结点 exactly 一次
对于每个结点，只进行常数时间的交换操作
设二叉树有N个结点，则总时间复杂度为O(N)

空间复杂度：O(N)¶

分析过程：
主要消耗在递归调用栈的空间
最坏情况下（完全不平衡的二叉树，退化为链表），递归深度为N，空间复杂度为O(N)
最好情况下（完全平衡的二叉树），递归深度为logN，空间复杂度为O(logN)
综合考虑，空间复杂度为O(N)

相关知识点延伸¶

1. 迭代实现方式（使用栈）¶

C
/**
 * 迭代方式交换二叉树左右子树
 * @param root 二叉树根结点
 */
void swapSubtreesIterative(BiTree root) {
    if (root == NULL) return;

    Stack s;  // 假设有栈结构
    initStack(&s);
    push(&s, root);

    while (!isEmpty(&s)) {
        BiTree p = pop(&s);

        // 交换当前结点的左右子树
        BiTree temp = p->lchild;
        p->lchild = p->rchild;
        p->rchild = temp;

        // 将子结点入栈（注意入栈顺序）
        if (p->lchild != NULL) push(&s, p->lchild);
        if (p->rchild != NULL) push(&s, p->rchild);
    }
}

2. 层序遍历实现（使用队列）¶

C
/**
 * 层序遍历方式交换二叉树左右子树
 * @param root 二叉树根结点
 */
void swapSubtreesLevelOrder(BiTree root) {
    if (root == NULL) return;

    Queue q;  // 假设有队列结构
    initQueue(&q);
    enqueue(&q, root);

    while (!isEmpty(&q)) {
        BiTree p = dequeue(&q);

        // 交换当前结点的左右子树
        BiTree temp = p->lchild;
        p->lchild = p->rchild;
        p->rchild = temp;

        // 将子结点入队
        if (p->lchild != NULL) enqueue(&q, p->lchild);
        if (p->rchild != NULL) enqueue(&q, p->rchild);
    }
}

3. 交换特定深度的子树¶

C
/**
 * 交换指定深度的结点的左右子树
 * @param p 当前处理的二叉树结点
 * @param targetDepth 目标深度（根结点深度为1）
 * @param currentDepth 当前深度
 */
void swapSubtreesAtDepth(BiTree p, int targetDepth, int currentDepth) {
    if (p == NULL) return;

    if (currentDepth == targetDepth) {
        // 交换当前深度结点的左右子树
        BiTree temp = p->lchild;
        p->lchild = p->rchild;
        p->rchild = temp;
    } else if (currentDepth < targetDepth) {
        // 继续向下搜索
        swapSubtreesAtDepth(p->lchild, targetDepth, currentDepth + 1);
        swapSubtreesAtDepth(p->rchild, targetDepth, currentDepth + 1);
    }
}

4. 判断两棵树是否互为镜像¶

C
/**
 * 判断两棵二叉树是否互为镜像
 * @param p 第一棵树的结点
 * @param q 第二棵树的结点
 * @return 如果互为镜像返回true，否则返回false
 */
bool isMirror(BiTree p, BiTree q) {
    // 两个都为空，则互为镜像
    if (p == NULL && q == NULL) {
        return true;
    }

    // 一个为空，另一个不为空，则不互为镜像
    if (p == NULL || q == NULL) {
        return false;
    }

    // 值相等，且左子树与右子树互为镜像
    return (p->data == q->data) &&
           isMirror(p->lchild, q->rchild) &&
           isMirror(p->rchild, q->lchild);
}

关键要点总结¶

递归思想：每个结点的处理都是相同的模式——交换左右子树，然后递归处理子树
遍历顺序：可以使用前序、后序遍历，但不能使用中序遍历（因为会重复交换）
指针操作：熟练掌握指针的交换操作
边界条件：正确处理空结点的情况
完全性：确保每个结点都被处理到

这个算法是二叉树的经典操作之一，体现了递归处理树结构的优雅性。理解其工作原理有助于掌握更复杂的树操作算法。