设计一个算法使二叉树每个节点的左孩子和右孩子交换,用C/C++
时间: 2023-11-14 14:06:48 浏览: 38
可以使用递归的方式交换每个节点的左右孩子。具体实现可以参考以下代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
void swap(TreeNode *node) {
if (node == NULL) {
return;
}
TreeNode *temp = node->left;
node->left = node->right;
node->right = temp;
swap(node->left);
swap(node->right);
}
void inorderTraversal(TreeNode *root) {
if (root == NULL) {
return;
}
inorderTraversal(root->left);
printf("%d ", root->val);
inorderTraversal(root->right);
}
int main() {
// 构造二叉树
TreeNode *root = (TreeNode *)malloc(sizeof(TreeNode));
root->val = 1;
root->left = (TreeNode *)malloc(sizeof(TreeNode));
root->left->val = 2;
root->left->left = (TreeNode *)malloc(sizeof(TreeNode));
root->left->left->val = 4;
root->left->right = (TreeNode *)malloc(sizeof(TreeNode));
root->left->right->val = 5;
root->right = (TreeNode *)malloc(sizeof(TreeNode));
root->right->val = 3;
root->right->left = (TreeNode *)malloc(sizeof(TreeNode));
root->right->left->val = 6;
root->right->right = (TreeNode *)malloc(sizeof(TreeNode));
root->right->right->val = 7;
// 交换左右孩子
swap(root);
// 遍历二叉树
inorderTraversal(root);
printf("\n");
return 0;
}
```
该算法的时间复杂度为 $O(n)$,其中 $n$ 为二叉树的节点数。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)