设计在链式存储结构上交换二叉树中所有结点左右子树的算法

在链式存储结构（如二叉链表）的二叉树中交换所有节点的左右子树是一个常见的操作，也称为“翻转”或“镜像”操作。以下是递归算法的一个简单步骤：

1. **基本情况**：
- 如果当前节点 `null` 或者其只有一个子节点，则不需要交换，直接返回。

2. **递归交换**：
- 对当前节点的左子节点（`left`）执行同样的操作，将 `left.right` 指向 `current`，然后 `left.left = current.right`（原左子树成为新的右子树）；
- 然后对当前节点的右子节点（`right`），将其 `right.left = current.left`（原右子树成为新的左子树），`right.right = current`（原根节点指向新的左子树）。

3. **更新指针**：
- 更新 `current` 的左右子节点为它们原本的对方，即 `current.left = right` 和 `current.right = left`。

4. **递归回溯**：
- 最后返回 `current.right` 继续处理父节点的右子节点，直到遍历到根节点。

这是个典型的递归过程，因为需要从叶子节点开始逐级向上进行调整。下面是伪代码形式：

function flipTree(node):
    if node is null or (node.left and node.right is null): // 基本情况
        return node

    // 递归交换左右子节点
    flippedLeft = flipTree(node.right)
    node.right.left = node.left
    node.left.right = flippedLeft
    node.left = flippedLeft.right
    node.right = node.left.left

    return node.right