设计一个递归算法，将二叉树所有结点的左，右子树交换

设计一个递归算法来交换二叉树的所有节点的左右子树，可以分为以下几个步骤：

1. **基本情况**: 如果节点为空，那么它就没有子树需要交换，直接返回。
2. **交换操作**: 对于非空节点，我们需要同时递归地交换它的左子树和右子树。
3. **递归调用**: 先递归处理左子树，然后处理右子树，最后交换左右子树的位置。

下面是一个简单的伪代码示例：

def swapSubtrees(root):
    if root is None:
        return None
    
    # 临时保存当前节点的左子树
    left = root.left
    # 交换左右子树
    root.left, root.right = root.right, root.left

    # 递归交换左子树的左右子树
    root.left = swapSubtrees(root.left)

    # 递归交换右子树的左右子树
    root.right = swapSubtrees(root.right)

    return root

这个函数会遍历整个二叉树，每次遇到一个节点都会先交换其左右子树，然后再递归地对子树进行同样的操作。这样下来，整个二叉树的结构就被彻底翻转了。

相关问题

用c语言编写设计一个递归算法，将二叉树所有结点的左，右子树交换

在C语言中，我们可以使用递归函数来实现二叉树节点左右子树的交换。首先，我们需要定义一个结构体表示二叉树的节点，包含值、左子节点和右子节点。然后，递归函数的基本思路是对当前节点执行交换操作，并对它的左右子节点分别递归地执行同样的操作。

以下是一个简单的二叉树节点结构体定义以及递归函数`swapSubtrees`：

#include <stdio.h>
#include <stdlib.h>

// 定义二叉树节点结构
typedef struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

// 递归函数，交换节点的左子树和右子树
void swapSubtrees(TreeNode** node) {
    if (*node == NULL) return; // 如果节点为空，直接返回

    // 交换左右子树
    TreeNode* temp = (*node)->left;
    (*node)->left = (*node)->right;
    (*node)->right = temp;

    // 对左子树和右子树递归调用自身
    swapSubtrees(&(*node)->left);
    swapSubtrees(&(*node)->right);
}

// 创建一个新的二叉树节点
TreeNode* createNode(int val) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    newNode->val = val;
    newNode->left = newNode->right = NULL;
    return newNode;
}

int main() {
    // 以示例创建一个二叉树并交换其子树
    TreeNode* root = createNode(1); // 根节点
    root->left = createNode(2);
    root->right = createNode(3);

    printf("Before swapping:\n");
    // 打印原始树结构（仅作示例）
    inorderTraversal(root);

    swapSubtrees(&root);

    printf("\nAfter swapping:\n");
    inorderTraversal(root);

    return 0;
}

// 中序遍历（仅用于测试打印）
void inorderTraversal(TreeNode* node) {
    if (node != NULL) {
        inorderTraversal(node->left);
        printf("%d ", node->val);
        inorderTraversal(node->right);
    }
}

在这个例子中，我们使用了`createNode`函数来创建新的节点，`inorderTraversal`函数来进行中序遍历以验证交换后的结果。`swapSubtrees`函数就是核心部分，它会递归地处理每个节点及其子节点。

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

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

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]