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

序列化二叉树

BM39 序列化二叉树
- 题目描述
- - 序列化
  - 反序列化
- 示例
- - 示例1
  - 示例2
- 解题思路
- - 序列化过程
  - 反序列化过程
- 代码实现
- 代码说明
- 复杂度分析
- 总结

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}

解题思路

序列化过程

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

反序列化过程

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

代码实现

#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;
}