编写一个递归算法，将用二叉链表表示的二叉树的所有结点的左、右子树交换。

好的，下面是递归算法的实现：

void swapTree(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    TreeNode* temp = root->left;
    root->left = root->right;
    root->right = temp;
    swapTree(root->left);
    swapTree(root->right);
}

其中，`TreeNode` 表示二叉树节点的结构体，包含 `left` 和 `right` 两个指向左右子树的指针。

首先判断根节点是否为空，如果是则直接返回。然后交换根节点的左右子树，并递归交换左右子树的子节点，直到遍历完整个二叉树为止。

可以通过以下方式调用该函数：

TreeNode* root = new TreeNode();
// 构建二叉树
swapTree(root);

注意，在使用该算法时，需要确保输入的二叉树是有效的，并且没有循环引用的情况。

相关问题

分别编写一个递归和非递归算法，求出二叉链表存储二叉树的叶子结点个数。满足要求的c代码如下：

### 回答1：
递归算法：

int countLeafNodes(BiTree T) {
    if (T == NULL) {
        return ;
    } else if (T->lchild == NULL && T->rchild == NULL) {
        return 1;
    } else {
        return countLeafNodes(T->lchild) + countLeafNodes(T->rchild);
    }
}

非递归算法：

int countLeafNodes(BiTree T) {
    int count = ;
    if (T == NULL) {
        return ;
    }
    Stack s;
    InitStack(&s);
    Push(&s, T);
    while (!IsEmpty(s)) {
        BiTree p;
        Pop(&s, &p);
        if (p->lchild == NULL && p->rchild == NULL) {
            count++;
        }
        if (p->rchild != NULL) {
            Push(&s, p->rchild);
        }
        if (p->lchild != NULL) {
            Push(&s, p->lchild);
        }
    }
    return count;
}

### 回答2：
非递归算法：

// 定义二叉链表结构
typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

// 求二叉链表存储二叉树的叶子结点个数的非递归算法
int countLeaves(Node* root) {
    if (root == NULL) {
        return 0;
    }
    
    int count = 0;
    Node* stack[100];  // 使用栈来实现非递归
    int top = -1;
    Node* curr = root;
    while (curr != NULL || top != -1) {
        while (curr != NULL) {
            stack[++top] = curr;
            curr = curr->left;
        }
        
        curr = stack[top--];
        if (curr->left == NULL && curr->right == NULL) {
            count++;
        }
        
        curr = curr->right;
    }
    
    return count;
}

递归算法：

// 定义二叉链表结构
typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

// 求二叉链表存储二叉树的叶子结点个数的递归算法
int countLeaves(Node* root) {
    if (root == NULL) {
        return 0;
    }
    
    if (root->left == NULL && root->right == NULL) {
        return 1;
    }
    
    return countLeaves(root->left) + countLeaves(root->right);
}

上述两个函数都接受一个二叉链表表示的二叉树的根节点作为参数，计算叶子结点的数量并返回。非递归算法使用栈来模拟递归的过程，逐个遍历树的节点，如果节点没有左子节点和右子节点，则计数器加1。递归算法则是递归地遍历左子树和右子树，并将返回的叶子节点数量相加。

### 回答3：
递归算法如下：

#include <stdio.h>

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

int countLeafNodes(struct TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    if (root->left == NULL && root->right == NULL) {
        return 1;
    }
    return countLeafNodes(root->left) + countLeafNodes(root->right);
}

int main() {
    // 构造一个二叉树
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = 1;
    root->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->left->val = 2;
    root->left->left = NULL;
    root->left->right = NULL;
    root->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->right->val = 3;
    root->right->left = NULL;
    root->right->right = NULL;
    
    int count = countLeafNodes(root);
    printf("叶子结点个数：%d\n", count);
    
    return 0;
}

非递归算法如下：

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

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

int countLeafNodes(struct TreeNode* root) {
    if (root == NULL) {
        return 0;
    }
    
    struct TreeNode* stack[100];  // 定义一个栈来存储遍历的结点
    int top = -1;  // 栈顶指针初始化为-1
    int count = 0;  // 叶子结点个数初始化为0
    
    stack[++top] = root;  // 根结点入栈
    
    while (top > -1) {
        struct TreeNode* node = stack[top--];  // 取出栈顶结点
        
        if (node->left == NULL && node->right == NULL) {
            count++;  // 如果当前结点没有左右子结点，则为叶子结点，个数加一
        }
        
        if (node->right) {
            stack[++top] = node->right;  // 右子结点入栈
        }
        
        if (node->left) {
            stack[++top] = node->left;  // 左子结点入栈
        }
    }
    
    return count;
}

int main() {
    // 构造一个二叉树
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = 1;
    root->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->left->val = 2;
    root->left->left = NULL;
    root->left->right = NULL;
    root->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->right->val = 3;
    root->right->left = NULL;
    root->right->right = NULL;
    
    int count = countLeafNodes(root);
    printf("叶子结点个数：%d\n", count);
    
    return 0;
}

已知二叉树采用二叉链表存储结构，编写一个算法交换二叉树所有左、右子树的位置，即结点的左子树变为结点的右子树，右子树变为左子树。

算法步骤：

1. 如果二叉树为空，直接返回。

2. 如果二叉树不为空，交换当前结点的左右子树。

3. 递归交换当前结点的左子树和右子树。

代码实现：

void swapTree(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    TreeNode* temp = root->left;
    root->left = root->right;
    root->right = temp;
    swapTree(root->left);
    swapTree(root->right);
}