链接：https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/solution/by-xun-ge-v-dyrv/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 

题目

示例

思路

解题思路
对于树的相关问题递归基本上都可以解决，递归能解决的问题迭代基本上也可以解决
所以对于本题有两种方向

1. 递归->深度优先搜索

        深度优先搜索又可以分为

•         先序遍历
•         中序遍历
•         后序遍历

1. 迭代->广度优先搜索

        广度优先搜索

•         层次遍历

具体实现

递归->深度优先搜索
这里我们寻找先序遍历，因为先序遍历优先处理根节点，对于后序构造树比较方便
遍历整个树元素，将对应树元素存储在字符串中，应当注意树元素为整型而存储在字符串中需要对其进行转换，对于空节点我们自定义 @ 表示，两个节点之间的数据用 ， 隔开。
反构造树，也是以先序遍历顺序，先构造根节点，然后构造左右节点

迭代->广度优先搜索
大体思路和递归差不多，根据树的层次遍历，访问树的节点，将树中节点存储在字符串数组中
反构造时按层次遍历方向构造

还有两种特殊解法看代码

代码

递归->深度优先搜索

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

void dfs(struct TreeNode * root, char * str)
{
    if(root == NULL)//空节点，用@代替
    {
        strcat(str, "@");
        strcat(str, ",");
        return;
    }
    char s[7] = "";//临时保存树元素值
    sprintf(s, "%d,", root->val);//类型转换
    strcat(str, s);//加入字符串数组中
    dfs(root->left, str);//递归遍历左右子节点
    dfs(root->right, str);
    return;
}

/** Encodes a tree to a single string. */
char* serialize(struct TreeNode* root) {
    char * str = calloc(500000,sizeof(char));//申请额外空间。并对其初始化为0
    dfs(root, str);//先序遍历
    return str;
}
struct TreeNode * dfsTree(char * data, int * inode)//先序遍历反构造树
{
    if(data[*inode] == '@')//空节点，构造
    {
        (*inode) += 2;跳过‘@和，’
        return NULL;
    }
    char s[7] = "";//临时保存元素值
    int node = 0;
    for(*inode; data[(*inode)] != ','; (*inode)++)//读取树元素值
    {
        s[node++] = data[*inode];
    }
    (*inode)++;//跳过‘，’
    struct TreeNode * root = malloc(sizeof(struct TreeNode));//构造节点
    root->val = atoi(s);//元素转换
    root->left = dfsTree(data, inode);//构造左右子节点
    root->right = dfsTree(data, inode);
    return root;
}
/** Decodes your encoded data to tree. */
struct TreeNode* deserialize(char* data) {
    int inode = 0;
    return dfsTree(data, &inode);
}

// Your functions will be called as such:
// char* data = serialize(root);
// deserialize(data);

作者：xun-ge-v
链接：https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/solution/by-xun-ge-v-dyrv/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

迭代->广度优先搜索

//BFS模拟传统层序遍历进行反序列化，即序列化使用层序遍历将二叉树的节点按顺序转换为字符串，反序列化先将字符串的值先转换为节点值，再将节点值按层序遍历的顺序反向生成二叉树
#define queue_size 50000
#define data_size 80000     //这个如果根据示例不同调整大小的话会节省空间

//序列化函数，该函数时将二叉树转换为字符串，具体方法是层序遍历，利用队列先入先入先出的特点，将每一层的节点放入队列中，先将当前节点值拼接到字符中，再将数组中队列的下一层的左右子节点支放入队列中，不断轮询直到所有节点均写入字符中返回
char* serialize(struct TreeNode* root){
    char* data=(char*)malloc(data_size*sizeof(char));
    data[0]='\0';   //为了方便后面使用strcat
    if(root==NULL){
        return data;
    }
    
    int head=0; //队列首
    int tail=0; //队列尾
    struct TreeNode* queue[queue_size];
    queue[tail++]=root;
    char temp[10];
    int flag=0; //用来标记是否是第一个字符
    while(head!=tail){
        //队首节点非空
        if(queue[head]!=NULL){
            //除了第一个位置不需要补','外，其余字符之间需要补上','，将','写入到结果字符串
            if(flag==1){
                strcat(data,","); 
            }
            flag=1;
            sprintf(temp,"%d",queue[head]->val);
            strcat(data,temp);
            //当前节点的左右子节点入队
            queue[tail++]=queue[head]->left;
            queue[tail++]=queue[head]->right;
        }
        //队首节点为空
        else{
            //null字符输出到data
            strcat(data,","); 
            strcat(data,"null");
        }
        //队列头部指针后移
        head++;
    }

    return data;
}

//反序列化函数，该函数时将字符串转换为二叉树，首先从字符串中提取所有节点值，再使用层序遍历，根据队列的情况，反向生成二叉树，思路是根据序列化函数判断，队列中的值是根据当前层序从左到右，不同层序从上到下的顺序放置，就将头指针定义为根节点，尾指针后移寻找左右子节点，根据头尾指针的情况，从上到下生成新的二叉树
struct TreeNode* deserialize(char* data) {
    if(data[0]=='\0'){
        return NULL;
    }

    //将字符串读入数组
    int nums[queue_size]={0};
    int nums_pos=0; //从第1位开始写，转换成树的时候比较方便
    int data_pos=0;
    char temp[10];
    int temp_pos=0;
    while(data[data_pos]!='\0'){
        temp_pos=0;
        //当遇到','时直接跳过
        if(data[data_pos]==','){
            data_pos++;
        }
        //将节点值从字符串中提取出来，放入中间字符串中用于转换数字
        while(data[data_pos]!=','&&data[data_pos]!='\0'){
            temp[temp_pos]=data[data_pos];
            temp_pos++;
            data_pos++;
        }
        temp[temp_pos]='\0';
        //如果为空节点
        if(strcmp("null",temp)==0){
            nums[nums_pos]=INT_MIN;
            nums_pos++;
        }
        //如果节点非空
        else{
            //sscanf()函数作用时提取字符串中数据
            sscanf(temp,"%d",&nums[nums_pos]);
            nums_pos++;
        }
    }
    //将数组输出成树
    struct TreeNode* queue[queue_size];  //存储节点地址的队列
    //先生成根节点，以便返回结果
    struct TreeNode* root=(struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val=nums[0];
    root->left=NULL;
    root->right=NULL;
    queue[0]=root;
    int head=0; //队列首
    int tail=1; //队列尾
    int pos=1;  //nums数组位置
    struct TreeNode* ret=root;
    //模拟树的层序遍历进行反向建树
    while(head!=tail){
        //如果节点不为空，从nums数组中读取两个元素
        if(queue[head]!=NULL){
            //左孩子
            struct TreeNode* left_child;
            //左孩子非空
            if(nums[pos]!=INT_MIN){
                left_child=(struct TreeNode*)malloc(sizeof(struct TreeNode));
                left_child->val=nums[pos];
            }
            //左孩子为空
            else{
                left_child=NULL;
            }
            queue[head]->left=left_child;
            queue[tail++]=left_child;
            pos++;

            //右孩子
            struct TreeNode* right_child;
            //右孩子非空
            if(nums[pos]!=INT_MIN){
                right_child=(struct TreeNode*)malloc(sizeof(struct TreeNode));
                right_child->val=nums[pos];
            }
            //左孩子为空
            else{
                right_child=NULL;
            }
            queue[head]->right=right_child;
            queue[tail++]=right_child;
            pos++;
        }
        //空不空都弹出队列首节点
        head++;
    }

    return ret;
}


作者：xun-ge-v
链接：https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/solution/by-xun-ge-v-dyrv/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

还有两种特殊解法看代码

//取巧解法，直接进行强制类型转换，将二叉树和字符串进行强制转换
char* serialize(struct TreeNode* root) {
    return  (char *)root;
}

struct TreeNode* deserialize(char* data) {
    return (struct TreeNode *)data;
}


作者：xun-ge-v
链接：https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/solution/by-xun-ge-v-dyrv/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

//还可以通过全局变量
struct TreeNode* hhh;
char* serialize(struct TreeNode* root) {
    hhh=root;
    return "";
}

struct TreeNode* deserialize(char* data) {
    return hhh;
}

作者：xun-ge-v
链接：https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/solution/by-xun-ge-v-dyrv/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。