首页 > 试题广场 >

序列化二叉树

[编程题]序列化二叉树
  • 热度指数：479433 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
请实现两个函数，分别用来序列化和反序列化二叉树，不对序列化之后的字符串进行约束，但要求能够根据序列化之后的字符串重新构造出一棵与原二叉树相同的树。

二叉树的序列化(Serialize)是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树等遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#）

二叉树的反序列化(Deserialize)是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。

例如，可以根据层序遍历的方案序列化，如下图:
层序序列化(即用函数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}

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息
算法知识视频讲解
添加回答
C
一个优雅的程序猿头像 一个优雅的程序猿 
void preSerialize(struct TreeNode* root, unsigned char *buf, int *bufLen) {
    if(root==NULL) {
        buf[(*bufLen)++]=1;
        return;
    }
    buf[(*bufLen)++] = root->val+2;
    preSerialize(root->left, buf, bufLen);
    preSerialize(root->right, buf, bufLen);
}
char* Serialize(struct TreeNode* root ) {
    unsigned char *buf;
    int bufLen=0;
    if(root==NULL)
        return "";
    buf = (unsigned char*)malloc(1000000);
    preSerialize(root, buf, &bufLen);
    buf[bufLen]=0;
    return (char*)buf;
}

struct TreeNode* preDeserialize(unsigned char *buf, int *bufLen) {
    struct TreeNode* res=NULL;
    if(bufLen==0) 
        return NULL;
        
    if(buf[*bufLen]==1) 
        (*bufLen)++;
    else {
        res = (struct TreeNode*)malloc(sizeof(struct TreeNode));
        res->val = buf[(*bufLen)++]-2;
        res->left = preDeserialize(buf, bufLen);
        res->right = preDeserialize(buf, bufLen);
    }
    return res;
}
struct TreeNode* Deserialize(char* str ) {
    struct TreeNode* root=NULL;
    int bufLen = 0;       
    if(strlen(str)==0)
        return NULL;
    root = preDeserialize((unsigned char*)str, &bufLen);
    return root;
}
抄你的
编辑于 2024-03-17 12:56:31 回复(0)
C
牛客218521332号头像 牛客218521332号 
/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param root TreeNode类 
 * @return char字符型一维数组
 */
#include <stdio.h>
#include <stdlib.h>
void PreOrderTraverse(struct TreeNode *root, int* index, char *buffer) {
    if (root == NULL) {
        buffer[*index] = '#';
        *index += 1;
        return;
    }
    buffer[*index] = (char)root->val;
    *index += 1;
    PreOrderTraverse(root->left, index, buffer);
    PreOrderTraverse(root->right, index, buffer);
}
char* Serialize(struct TreeNode* root ) {
    // write code here
    int index = 0;
    char *buffer = (char*)malloc(sizeof(char) * 1000);
    PreOrderTraverse(root, &index, buffer);
    buffer[index + 1] = '\0';
    return buffer;
}
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param str char字符型一维数组 
 * @return TreeNode类
 */
struct TreeNode *DeserializeHelper(char *str, int* index) {
    if (str[*index] == '#') {
        *index += 1;
        return NULL;
    }
    if (str[*index] == '\0') {
        return NULL;
    }
    struct TreeNode *root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = (int)((unsigned char)str[*index]);
    *index += 1;
    root->left = DeserializeHelper(str, index);
    root->right = DeserializeHelper(str, index);
    return root;
}
struct TreeNode* Deserialize(char* str ) {
    // write code here
    int index = 0;
    return DeserializeHelper(str, &index);   
}

编辑于 2024-01-03 22:03:45 回复(0)
C
芸某头像 芸某
头铁做法。。
开大空间做层序遍历
记得char的范围是-128~127 遇到负数要+256 
/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param root TreeNode类
 * @return char字符型一维数组
 */
#include <stdio.h>
#include <stdlib.h>
int NNodes(struct TreeNode* root) {
    int rtn = 2;
    if (root == NULL) {
        return 1;
    }
    return rtn * (NNodes(root->left)>NNodes(root->right)?NNodes(root->left):NNodes(root->right));
}

char* Serialize(struct TreeNode* root ) {
    // write code here
    int nodeNum = NNodes(root) -1;
    if(nodeNum == 0){
        return NULL;
    }
    int rtnLen = 2 + nodeNum*2 ;
    char* rtn = (char*)malloc(sizeof(char) * rtnLen);
    struct TreeNode** nodelist= (struct TreeNode**)malloc(sizeof(root) * nodeNum);
    rtn[0] = '{';
    nodelist[0] = root;
    //层序遍历
    int i = 0,j = 1;
    while(i<j){
        if(nodelist[i]!=NULL){
            rtn[i*2 + 1] = nodelist[i]->val;   
        }else{
            rtn[i*2 + 1] = '#';
        }
        if(i*2 + 2 < rtnLen - 2){
                rtn[i*2+2] = ',';
        }
        if(j<nodeNum&&nodelist[i]!=NULL){
            nodelist[j++] = nodelist[i]->left;
            nodelist[j++] = nodelist[i]->right;
        }
        i++;
    }rtn[i*2] = '}';rtn[i*2+1] = '\0';
    return rtn;
}

struct TreeNode* Deserialize(char* str ) {
    // write code here
    int strlen = 0;
    if(str==NULL){
        return NULL;
    }
    while(str[strlen]!='\0'){
        strlen++;
    }
    struct TreeNode** nodelist = (struct TreeNode**)malloc(sizeof(struct TreeNode*) * strlen);
    int i,j;
    i = 1;j = 0;
    while(i<strlen){
        if(str[i] == '{' || str[i] == '}' || str[i] == ','){
            i+=2;
            continue;
        }else{
            if(str[i]!='#'){
                nodelist[j] = (struct TreeNode*)malloc(sizeof(struct TreeNode));
                nodelist[j]->val = str[i]>0?str[i]:(str[i]+256);
            }
            else{
                nodelist[j] = NULL;
            }
        }
        i+=2;
        j++;
    }
    i = 0;
    int empty = 0;
    while(i<j){
        if(nodelist[i]!=NULL){
            nodelist[i]->left = nodelist[i*2+1 - empty];
            nodelist[i]->right = nodelist[i*2+2 - empty];
        }else{
            empty +=2;
        }i++;
    }
    return nodelist[0];
}


发表于 2023-09-26 20:39:48 回复(0)
C
牛客780307272号头像 牛客780307272号
纯C写的，序列化和反序列化都用的前序，解释也很详细，希望能帮到迷茫的你，帮得上忙扣个1 
const char null_str[]="#";
void create_str(char* str,struct TreeNode* root,int* i){
    char* s=(char*)malloc(sizeof(char)*4);
    int len=strlen(null_str);
    if(root==NULL){
        memcpy(str+*i,null_str,len);//把str+*i开始的len个位置复制成*null_str
        str[*i+1]=',';
        *i+=len+1;
    }
    else{
        int k=0;
        if(root->val==0) str[(*i)++]=root->val+'0';
        //这里是处理万一val是0，下面的while循环就直接结束了
        else{
            if(root->val<0) str[(*i)++]='-';//有负数的情况
            while(root->val){//开辟一个空间，把val从低位存到高位，abs是求绝对值
                s[k++]=abs(root->val)%10+'0';
                root->val/=10;
            }
            while(k) str[(*i)++]=s[--k];//从s里面的高位开始存到str里面
        }
        str[(*i)++]=',';
        create_str(str,root->left,i);
        create_str(str,root->right,i);
    }
}
char* Serialize(struct TreeNode* root ) {
    if(root==NULL)
        return NULL;
    char* data=(char*)malloc(sizeof(char)*101);
    int i=0;//i是用来记录字符串位置
    create_str(data,root,&i);
    data[i]=0;//结尾给个终止符
    return data;
}
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param str char字符型一维数组 
 * @return TreeNode类
 */

struct TreeNode* createtree(char* str, int *p){
    if(str[*p]=='#'){
        (*p)+=2;
        return NULL;
    }
    int i;
    if(str[*p]=='-'){//处理负数的情况
        i=-1;
        (*p)++;
    }
    else i=1;
    struct TreeNode*root=(struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val=0;
    while(str[*p]!=',')
        root->val=root->val*10+str[(*p)++]-'0';//把字符一位一位转换成数字
    root->val*=i;
    *p+=1;//逗号的间隔
    root->left=createtree(str, p);
    root->right=createtree(str, p);
    return root;
}
struct TreeNode* Deserialize(char* str ) {
    if(str==NULL)
        return NULL;
    int i=0;//i是用来记录字符串访问到哪里
    return createtree(str,&i);
}

发表于 2022-07-06 23:37:36 回复(0)
提交观点

问题信息

队列 树
难度：
7条回答 110577浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号