用Python代码实现设计在链式存储结构上交换二叉树中所有结点左、右子 树的算法

实现交换二叉树中所有节点的左右子树，可以采用递归算法实现，代码如下：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def exchange_tree(root: TreeNode) -> TreeNode:
    if not root:
        return None
    # 交换左右子树
    root.left, root.right = root.right, root.left
    # 递归交换左右子树
    exchange_tree(root.left)
    exchange_tree(root.right)
    return root

其中，TreeNode是二叉树节点的定义，exchange_tree函数实现了交换二叉树中所有节点的左右子树。在函数中，我们首先判断当前节点是否为空，如果为空则直接返回。接着交换当前节点的左右子树，然后递归交换当前节点的左右子树。最后返回根节点即可。

相关问题

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

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

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

编写递归算法,将二叉树中所有结点的左右右子 树相互交换。

可以按照以下步骤编写递归算法：

1. 首先检查根节点是否为空，如果为空则返回。

2. 交换当前节点的左右子树。

3. 递归调用函数，分别传入当前节点的左子树和右子树。

下面是示例代码：

def swap_tree(root):
    if root is None:
        return
    
    # 交换左右子树
    root.left, root.right = root.right, root.left
    
    # 递归处理左右子树
    swap_tree(root.left)
    swap_tree(root.right)

可以通过以下方式测试算法：

# 定义二叉树节点类
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 构造二叉树
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)

# 打印交换前的中序遍历结果
inorder_before = []
def inorder_traversal(root):
    if root is None:
        return
    inorder_traversal(root.left)
    inorder_before.append(root.val)
    inorder_traversal(root.right)
inorder_traversal(root)
print("交换前的中序遍历结果：", inorder_before)

# 执行交换函数
swap_tree(root)

# 打印交换后的中序遍历结果
inorder_after = []
inorder_traversal(root)
print("交换后的中序遍历结果：", inorder_after)

输出结果应该为：

交换前的中序遍历结果： [4, 2, 5, 1, 6, 3, 7]
交换后的中序遍历结果： [7, 3, 6, 1, 5, 2, 4]