剑指offer(C++)-JZ37:序列化二叉树(数据结构-树)

简介: 剑指offer(C++)-JZ37:序列化二叉树(数据结构-树)

题目描述:

请实现两个函数,分别用来序列化和反序列化二叉树,不对序列化之后的字符串进行约束,但要求能够根据序列化之后的字符串重新构造出一棵与原二叉树相同的树。


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


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


例如,可以根据层序遍历的方案序列化,如下图:

层序序列化(即用函数Serialize转化)如上的二叉树转为"{1,2,3,#,#,6,7}",再能够调用反序列化(Deserialize)将"{1,2,3,#,#,6,7}"构造成如上的二叉树。


当然你也可以根据满二叉树结点位置的标号规律来序列化,还可以根据先序遍历和中序遍历的结果来序列化。不对序列化之后的字符串进行约束,所以欢迎各种奇思妙想。


数据范围:节点数 n≤100,树上每个节点的值满足0≤val≤150


要求:序列化和反序列化都是空间复杂度 O(n),时间复杂度O(n)

示例:

输入:

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


返回值:

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

解题思路:

本题考察数据结构树的使用。题目通过序列化函数和反序列化函数完成,分别说明。


序列化:将二叉树转换为字符串形式,空的节点用#表示;借用队列特性进行二叉树遍历,统计空节点个数,当空节点个数和队列内数据个数一致时,说明到达最后一层,且全是#,最后一排#就不存放进vector了;将string转换为char,序列化就结束了,最后应该以逗号结尾。


反序列化:判空;获取根节点;根据字符串中每个节点后面跟着一个逗号的特性,可以快速遍历节点,并存放进vector中;因为vector是一层层的排序,还需要连接节点与其左右子树,写一个循环即可解决,反序列化完成。


如果有同学想要使序列化的字符串不以逗号结尾,除了更改序列化函数,还要更改反序列化函数哦,不然使用substr函数会越界。

测试代码:

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    // 序列化
    char* Serialize(TreeNode *root) 
    {    
        if(root==nullptr)
            return "#";
        string result;
        int nullcount=0;
        // 获取根节点
        queue<TreeNode*> q;
        q.push(root);
        // 遍历二叉树
        // 当队列尺寸和空节点数一致时,说明到最后一层了
        while(q.size()!=nullcount)
        {
            TreeNode* f=q.front();
            result+=GetChar(f);
            q.pop();
            if(f!=nullptr)
            {
                q.push(f->left);
                q.push(f->right);
                if(f->left==nullptr)
                    nullcount++;
                if(f->right==nullptr)
                    nullcount++;
            }
            else
            {
                q.push(nullptr);
                q.push(nullptr);
                nullcount++;
            }
        }
        char *r=new char[result.length()+1];
        for(int i=0;i<result.length();++i)
            r[i]=result[i];
        r[result.length()]='\0';
        return r;
    }
    // 反序列化
    TreeNode* Deserialize(char *str) 
    {
        // 判空
        if(str==nullptr)
            return nullptr;
        string s(str);
        if(str[0]=='#')
            return nullptr;
        // 获取根节点
        vector<TreeNode*> v;
        TreeNode* r=new TreeNode(atoi(s.c_str()));
        v.push_back(r);
        s=s.substr(s.find_first_of(',')+1);
        // 获取节点
        while(!s.empty())
        {
            if(s[0]=='#')
            {
                v.push_back(nullptr);
                s=s.substr(2);
            }
            else
            {
                TreeNode* temp=new TreeNode(atoi(s.c_str()));
                v.push_back(temp);
                s=s.substr(s.find_first_of(',')+1);
            }
        }
        // 连接左右子树
        int i=0;
        int size=v.size();
        while((i+1)*2-1<size)
        {
            if(v[i]==nullptr)
            {
                i++;
                continue;
            }
            v[i]->left=v[(i+1)*2-1];
            v[i]->right=v[(i+1)*2];
            i++;
        }
        return v[0];
    }
    // 获取节点字符
    string GetChar(TreeNode* f)
    {
        if(f==nullptr)
            return "#,";
        else 
            return to_string(f->val)+",";
    }
};


相关文章
|
27天前
|
存储 算法 搜索推荐
探索常见数据结构:数组、链表、栈、队列、树和图
探索常见数据结构:数组、链表、栈、队列、树和图
84 64
|
20天前
|
存储 算法 关系型数据库
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
这篇文章主要介绍了多路查找树的基本概念,包括二叉树的局限性、多叉树的优化、B树及其变体(如2-3树、B+树、B*树)的特点和应用,旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
14 0
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
|
28天前
【高阶数据结构】二叉树进阶探秘:AVL树的平衡机制与实现详解(三)
【高阶数据结构】二叉树进阶探秘:AVL树的平衡机制与实现详解
|
28天前
【高阶数据结构】二叉树进阶探秘:AVL树的平衡机制与实现详解(二)
【高阶数据结构】二叉树进阶探秘:AVL树的平衡机制与实现详解
|
17天前
|
Java C++
【数据结构】探索红黑树的奥秘:自平衡原理图解及与二叉查找树的比较
本文深入解析红黑树的自平衡原理,介绍其五大原则,并通过图解和代码示例展示其内部机制。同时,对比红黑树与二叉查找树的性能差异,帮助读者更好地理解这两种数据结构的特点和应用场景。
22 0
|
20天前
|
存储 算法
数据结构与算法学习十六:树的知识、二叉树、二叉树的遍历(前序、中序、后序、层次)、二叉树的查找(前序、中序、后序、层次)、二叉树的删除
这篇文章主要介绍了树和二叉树的基础知识,包括树的存储方式、二叉树的定义、遍历方法(前序、中序、后序、层次遍历),以及二叉树的查找和删除操作。
16 0
|
22天前
05(数据结构考研)树相关操作代码
05(数据结构考研)树相关操作代码
26 0
|
23天前
|
存储 算法 Java
数据结构和算法--分段树
数据结构和算法--分段树
11 0
|
26天前
【数据结构】翻转、平衡、对称二叉树,最大深度、判断两棵树是否相等、另一棵树的子树
【数据结构】翻转、平衡、对称二叉树,最大深度、判断两棵树是否相等、另一棵树的子树
24 0