设 B 是一棵采用链式结构存储的二叉树，编写一个交换 B 中所有结点左、右子树的函数。

[tag_link]

参考答案

采用后序思想，先递归处理左右子树，再交换当前结点的两个孩子指针，可原地得到镜像树。

伪代码

SwapChildren(T):
    if T == null: return
    SwapChildren(T.left)          // 先递归处理左右子树
    SwapChildren(T.right)
    temp = T.left
    T.left = T.right
    T.right = temp

复杂度

时间 O(n)，递归栈空间 O(h)。

边界条件

空树无需操作；单结点树不变；对结果再执行一次该算法会恢复原树。

易错点

若先交换当前结点再仍按旧指针含义递归，容易重复处理一侧或漏掉另一侧；后序写法最稳妥。

评分要点

遍历全部结点；每个结点只交换一次；递归出口正确；说明原地修改与复杂度。