每日一题——序列化二叉树

BM39 序列化二叉树

题目描述

请实现两个函数，分别用来序列化和反序列化二叉树。二叉树的序列化是将二叉树按照某种遍历方式转换为字符串格式，而反序列化则是根据字符串重建出原二叉树。

序列化

二叉树的序列化(Serialize)是指将二叉树转换为字符串，通常我们使用层序遍历的方式将树的节点值逐个保存。在序列化的过程中，用某种符号表示空节点（如#），例如：层序序列化的结果为"{1,2,3,#,#,6,7}"。

反序列化

二叉树的反序列化(Deserialize)是指根据序列化后的字符串重建出二叉树。例如，给定序列化字符串"{1,2,3,#,#,6,7}"，我们可以重新构造出与原二叉树相同的树结构。

示例

示例1

输入：

{1,2,3,#,#,6,7}

返回值：

{1,2,3,#,#,6,7}

示例2

输入：

{8,6,10,5,7,9,11}

返回值：

{8,6,10,5,7,9,11}

解题思路

序列化过程

1. 使用层序遍历的方式遍历二叉树。
2. 将每个节点的值转化为字符串，并用#表示空节点。
3. 将结果以逗号连接形成最终的字符串。

反序列化过程

1. 将序列化后的字符串按逗号分割。
2. 按照层序的顺序，逐个构建二叉树的节点。
3. 使用队列来辅助构建树的结构，按照层序遍历的方式将节点插入到对应的位置。

代码实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>// 定义二叉树节点
struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;
};// 定义队列节点
typedef struct QueueNode {struct TreeNode* treeNode;struct QueueNode* next;
} QueueNode;// 定义队列
typedef struct {QueueNode* front;QueueNode* rear;
} Queue;// 创建队列
Queue* createQueue() {Queue* q = (Queue*)malloc(sizeof(Queue));q->front = q->rear = NULL;return q;
}// 判断队列是否为空
int isEmpty(Queue* q) {return q->front == NULL;
}// 入队
void enqueue(Queue* q, struct TreeNode* node) {QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));newNode->treeNode = node;newNode->next = NULL;if (q->rear != NULL) {q->rear->next = newNode;}q->rear = newNode;if (q->front == NULL) {q->front = newNode;}
}// 出队
struct TreeNode* dequeue(Queue* q) {if (isEmpty(q)) {return NULL;}QueueNode* temp = q->front;struct TreeNode* node = temp->treeNode;q->front = q->front->next;if (q->front == NULL) {q->rear = NULL;}free(temp);return node;
}// 释放队列
void freeQueue(Queue* q) {while (!isEmpty(q)) {dequeue(q);}free(q);
}// 序列化二叉树
char* Serialize(struct TreeNode* root) {if (root == NULL) {return "#";}Queue* q = createQueue();enqueue(q, root);char* result = (char*)malloc(10000 * sizeof(char)); // 假设字符串长度足够char* buffer = (char*)malloc(100 * sizeof(char));int len = 0;while (!isEmpty(q)) {struct TreeNode* node = dequeue(q);if (node == NULL) {len += sprintf(result + len, "#,");} else {len += sprintf(result + len, "%d,", node->val);enqueue(q, node->left);enqueue(q, node->right);}}// 去掉最后一个逗号if (len > 0 && result[len - 1] == ',') {result[len - 1] = '\0';} else {result[len] = '\0';}free(buffer);freeQueue(q);return result;
}// 反序列化二叉树
struct TreeNode* Deserialize(char* data) {if (strcmp(data, "#") == 0) {return NULL;}char* token = strtok(data, ",");struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));root->val = atoi(token);root->left = root->right = NULL;Queue* q = createQueue();enqueue(q, root);while ((token = strtok(NULL, ",")) != NULL) {struct TreeNode* parent = dequeue(q);if (strcmp(token, "#") != 0) {struct TreeNode* leftNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));leftNode->val = atoi(token);leftNode->left = leftNode->right = NULL;parent->left = leftNode;enqueue(q, leftNode);}token = strtok(NULL, ",");if (token == NULL) {break;}if (strcmp(token, "#") != 0) {struct TreeNode* rightNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));rightNode->val = atoi(token);rightNode->left = rightNode->right = NULL;parent->right = rightNode;enqueue(q, rightNode);}}freeQueue(q);return root;
}

代码说明

1. 队列实现：为了方便按层次遍历二叉树，我们使用队列来存储树的节点。
2. 序列化函数 Serialize：使用层序遍历对树进行遍历，将节点值加入到结果字符串中。如果节点为空，则用#表示。
3. 反序列化函数 Deserialize：将序列化后的字符串按逗号分割，依次创建节点并建立左右子树。

复杂度分析

• 时间复杂度：O(n)，其中n是树的节点数。每个节点在序列化和反序列化过程中只被访问一次。
• 空间复杂度：O(n)，需要存储队列中的节点以及序列化后的字符串。

总结

本题考察了二叉树的序列化与反序列化，使用层序遍历来实现序列化和反序列化的方法，保证了在时间和空间复杂度上都能满足要求。这题的整体难度还是不小的，但是最主要的是队列的实现，这个完成，任务就完成一半。至于后面函数的实现，就是研究递归了。