给你二叉树的根结点 root ,请你将它展开为一个单链表: 展开后的单链表应该同样使用 TreeNode ,其中 right 子指针指向链表中下一个结点,而左子指针始终为 null 。 展开后的单链表应该与二叉树 先序遍历 顺序相同。用c语言实现一下
时间: 2024-12-15 13:26:54 浏览: 16
在C语言中,你可以通过递归的方式实现这个二叉树到单链表的转换。首先创建一个辅助函数,用于处理当前节点并将其添加到链表中。然后从根节点开始进行遍历。
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树节点结构
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// 辅助函数,用于添加当前节点到链表中
void flatten(TreeNode* root, TreeNode** head) {
if (root == NULL) return; // 空节点直接返回
// 如果右子节点存在,先处理右子树
if (root->right != NULL) {
flatten(root->right, head); // 递归处理右子树
TreeNode* cur = *head; // 获取当前处理到最后的节点
while (cur->right != NULL) cur = cur->right; // 跟踪右子树的最后一个节点
// 将当前节点连接到右子树的末尾
cur->right = root;
root->left = NULL; // 更新当前节点的左子指针为NULL
} else {
// 如果没有右子节点,直接将当前节点添加到链表头部
if (*head == NULL) {
*head = root;
} else {
TreeNode* prev = *head;
while (prev->right != NULL) prev = prev->right; // 找到插入位置
prev->right = root;
}
}
}
// 主函数
TreeNode* flattenTree(TreeNode* root) {
TreeNode* head = NULL;
flatten(root, &head);
return head;
}
int main() {
// 创建示例二叉树
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = 1;
root->left = (TreeNode*)malloc(sizeof(TreeNode));
root->left->val = 2;
root->right = (TreeNode*)malloc(sizeof(TreeNode));
root->right->val = 5;
root->left->left = (TreeNode*)malloc(sizeof(TreeNode));
root->left->left->val = 3;
root->left->right = (TreeNode*)malloc(sizeof(TreeNode));
root->left->right->val = 4;
// 展开二叉树并打印结果
TreeNode* flattenedHead = flattenTree(root);
while (flattenedHead != NULL) {
printf("%d ", flattenedHead->val);
flattenedHead = flattenedHead->right;
}
return 0;
}
```
在这个例子中,`flattenTree` 函数首先初始化一个空链表头 `head`,然后调用 `flatten` 函数进行实际的链表构造。`flatten` 函数会按照先序遍历的顺序把节点链接起来。
阅读全文