首页 > 试题广场 >

序列化二叉树

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

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

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

例如，可以根据层序遍历的方案序列化，如下图:
层序序列化(即用函数Serialize转化)如上的二叉树转为"{1,2,3,#,#,6,7}"，再能够调用反序列化(Deserialize)将"{1,2,3,#,#,6,7}"构造成如上的二叉树。

再举一个例子

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

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

数据范围：节点数 ，树上每个节点的值满足
要求：序列化和反序列化都是空间复杂度 ，时间复杂度
示例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，点此查看相关信息
算法知识视频讲解
添加回答
Python
牛客38477449号头像 牛客38477449号 
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def Serialize(self, root):
        # write code here
        if not root:
            return ''
        res = []
        import collections
        queue = collections.deque([root])
        while queue:
            node = queue.popleft()
            if node:
                res.append(str(node.val))
            else:
                res.append('#')
                continue
            if node.left:
                queue.append(node.left)
            else:
                queue.append(None)
            if node.right:
                queue.append(node.right)
            else:
                queue.append(None)
        return ','.join(res)
    def Deserialize(self, s):
        # write code here
        if s == '':
            return None
        import collections
        s = collections.deque(s.split(','))
        queue = collections.deque([])
        root = TreeNode(int(s.popleft()))
        p = root
        while s:
            node = s.popleft()
            if node != '#':
                root.left = TreeNode(int(node))
                queue.append(root.left)
            node = s.popleft()
            if node != '#':
                root.right = TreeNode(int(node))
                queue.append(root.right)
            if not queue:
                break
            root = queue.popleft()
        return p

发表于 2021-09-03 12:19:28 回复(0)
Python
DDooo头像 DDooo 
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    flag = -1
    def Serialize(self, root):
        # write code here
        if not root:
            return '#'
        return str(root.val) + ' ' + self.Serialize(root.left) + ' ' + self.Serialize(root.right)

    def Deserialize(self, s):
        # write code here
        self.flag +=1
        l = s.split(' ')
        if self.flag >= len(s):
            return None
        root = None
        if l[self.flag]!='#':
            root = TreeNode(int(l[self.flag]))
            root.left = self.Deserialize(s)
            root.right = self.Deserialize(s)
        return root

发表于 2020-08-06 19:54:29 回复(0)
Python
牛客1349号头像 牛客1349号
Python实现，讲真，这道题是有些难度的，我们用队列思想（append() + pop(0)）和树的先序遍历来搞定它
序列化：通过先序遍历将结点元素依次添加到队列中，结点存在添加节点，不存在添加 ‘#’，最后返回字符串（注意将树节点的值转化成字符串格式）
反序列化：先判断队列中是否还有元素，如果有判断是否是 ‘#’，如果是直接返回，如果不是，创建树节点（注意将队列中的字符串格式转换成数值类型），然后依次判断左右孩子，直至队列为空。 
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def Serialize(self, root):
        # write code here
        mid_list = []
        def dfs(node):
            if not node:
                mid_list.append('#')
                return
            mid_list.append(str(node.val))
            dfs(node.left)
            dfs(node.right)
        dfs(root)
        return ','.join(mid_list)
    def Deserialize(self, s):
        # write code here
        mid_list = s.split(',')
        def dfs():
            if mid_list:
                cur = mid_list.pop(0)
                if cur == '#':
                    return
                node = TreeNode(int(cur))
                node.left = dfs()
                node.right = dfs()
            return node
        return dfs()



发表于 2020-07-27 00:09:00 回复(0)
Python
Fzldq头像 Fzldq
拿JZ60的答案改一改就行 
class Solution:
    def Serialize(self, root):
        if not root:
            return '#!'
        s = ''
        cur = [root]
        while any(cur):
            next_lst = []
            for i in cur:
                if i:
                    s += str(i.val) + '!'
                    next_lst += [i.left, i.right]
                else:
                    s += '#!'
                    next_lst += [None, None]
            cur = next_lst
        return s

    def Deserialize(self, s):
        from collections import deque
        if s=='#!':
            return None
        s = deque(s.split('!'))
        s.pop()
        root = TreeNode(int(s.popleft()))
        cur = [root]
        while s:
            next_lst = []
            for i in cur:
                tmp_left = s.popleft()
                tmp_right = s.popleft()
                if i:
                    if tmp_left != '#':
                        i.left = TreeNode(int(tmp_left))
                    if tmp_right != '#':
                        i.right = TreeNode(int(tmp_right))
                    next_lst += [i.left, i.right]
                else:
                    next_lst += [None, None]
            cur = next_lst
        return root



发表于 2020-07-19 16:59:29 回复(0)
Python
黄沙遮天头像 黄沙遮天 
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    ss=[]
    def Serialize(self, root):
        # write code here
        if not root:
            #不知道为啥这里没有用！作为分隔
            return '#,'
        #这里是前序序列化递归的一个简易形式
        return str(root.val)+','+self.Serialize(root.left)+self.Serialize(root.right)
    def Deserialize(self, s):
        # write code here
        if len(s)==0:
            return None
        if s[0]=='#':
            #针对于root直接为空的形式
            return None
        self.ss=s.split(',')
        return self.reconstruct()
    def reconstruct(self):
        #采用的是前序反序列化的方法
        val=self.ss[0]
        if val=='#':
            #这作为返回条件
            self.ss=self.ss[1:]
            return None
        val=int(val)
        node1=TreeNode(val)
        self.ss=self.ss[1:]
        node1.left=self.reconstruct()
        node1.right=self.reconstruct()
        return node1
其实我真的想吐槽，这个题目中要求值以！结束，但是实际解答中很多人直接以，作为分隔。原先题目中的要求会造成麻烦，以为空指针和有值节点的差异性，不利于处理。本题采用的是前序遍历的方法，因为前序遍历中第一字符肯定是根节点，第二个字符肯定是根字符的左子树根节点，以此递归，就可以进行反序
发表于 2020-02-05 23:11:20 回复(0)
Python
天山剑客头像 天山剑客 
# -*- coding:utf-8 -*-
# 解体思路：递归实现二叉树前序遍历，前序遍历实现序列化与反序列化
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
class Solution:
    def Serialize(self, root):
        # write code here
        if root is None:
            return '#'

        return str(root.val) + '!' + self.Serialize(root.left) + '!' + self.Serialize(root.right)

    def Deserialize(self, s):
        # write code
        def deserialize(ls):
            if len(s) <= 0:
                return None

            root = None
            val = ls.pop(0)
            if val != '#':
                root = TreeNode(int(val))
                root.left = deserialize(ls)
                root.right = deserialize(ls)

            return root

        arr = s.split('!')
        return deserialize(arr)
    

发表于 2020-01-17 19:17:17 回复(0)
Python
秋水中的鱼头像 秋水中的鱼
用的先序遍历实现二叉树的序列化和反序列化
序列化就是把二叉树的每一个值用字符串形式拼接,以'!'分隔,'#'表示空节点
反序列化就是把序列化的字符串变成一颗二叉树,返回二叉树的根 
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def Serialize(self, root):
        if not root:
            return '#!'
        res=str(root.val)+'!'
        return res+self.Serialize(root.left)+self.Serialize(root.right)
        
    def Deserialize(self, s):
        l=s.split('!')
        def help(l):
            t=l.pop(0)
            if t=='#':
                return
            root=TreeNode(int(t))
            root.left=help(l)
            root.right=help(l)
            return root
        return help(l)


发表于 2019-11-20 08:55:59 回复(0)
Python
我要扛offer回家头像 我要扛offer回家 
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def __init__(self):
        self.flag=-1
    def Serialize(self, root):
        # write code here
        res=[]
        if not root:
            return '#'
        res.append(str(root.val))
        res.append(self.Serialize(root.left))
        res.append(self.Serialize(root.right))
        return ','.join(res)
    def Deserialize(self, s):
        # write code here
        self.flag+=1
        l=s.split(',')
        if self.flag>=len(s):
            return None
        root=None
        if l[self.flag]!='#':
            root=TreeNode(int(l[self.flag]))
            root.left=self.Deserialize(s)
            root.right=self.Deserialize(s)
        return root

发表于 2019-10-08 16:53:53 回复(0)
Python
呵呵哈201907301408785头像 呵呵哈201907301408785
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def Serialize(self, root):
        # write code here
        if not root: return []
        # validNode 节点数组中有效节点数
        nodeList, list, validNode = [root], [], 1
        while nodeList:
            if not validNode: break
            node = nodeList.pop(0)
            if node:
                validNode -= 1
                list.append(node.val)
                nodeList.append(node.left)
                nodeList.append(node.right)
                if node.left: validNode += 1
                if node.right: validNode += 1
            else:
                list.append("#")
        return list

    def Deserialize(self, s):
        # write code here
        if not s: return None
        # direction True:left False:right
        pHead, direction = TreeNode(s.pop(0)), True
        nodeList = [pHead]
        while s:
            nodeVal, node = s.pop(0), None
            if nodeVal != "#":
                node = TreeNode(nodeVal)
                nodeList.append(node)
            if direction:
                nodeList[0].left = node
            else:
                nodeList[0].right = node
                nodeList.pop(0)
            direction = not direction
        return pHead

编辑于 2019-08-22 14:20:40 回复(0)
Python
:)201902241824466头像 :)201902241824466
class Solution:
    def Serialize(self, root):
        # write code here
        return root
    def Deserialize(self, s):
        # write code here
        return s
发表于 2019-07-14 16:03:51 回复(0)
Python
亚斗梦头像 亚斗梦 
用的前序遍历，结果储存再stack里面
class Solution:
    stack = []
    def Serialize(self, root):
        if root:
            self.stack.append(root.val)
            self.Serialize(root.left)
            self.Serialize(root.right)
        else:self.stack.append('#')
        return self.stack
    def Deserialize(self, s):
        if s:
            node = TreeNode(0)
            if s[0] == '#':node = None
            else:node = TreeNode(s[0])
            s.pop(0)
            if s and node:
                node.left = self.Deserialize(s)
            if s and node:
                node.right = self.Deserialize(s)
            return node

发表于 2019-05-26 13:18:21 回复(0)
Python
poteman头像 poteman 
    def Serialize(self, root):
        if not root:
            return "#"
        return str(root.val) + ',' + self.Serialize(root.left) + ',' + self.Serialize(root.right)


    def Deserialize(self, s):

        root, index = self.DeHelper(s.split(","), 0)
        return root

    def DeHelper(self, s, idx):
        if s[idx] == "#":
            return None, idx + 1
        root = TreeNode(int(s[idx]))
        idx += 1
        root.left, idx = self.DeHelper(s, idx)
        root.right, idx = self.DeHelper(s, idx)

        return root, idx
发表于 2019-05-19 09:06:55 回复(0)
Python
Ponder_xu头像 Ponder_xu
class Solution:
    def Serialize(self, root):
        # write code here
        if not root:
            return '#'
        return str(root.val) + ',' + self.Serialize(root.left) + ',' + self.Serialize(root.right)

    def Deserialize(self, s):
        l=s.split(',')
        if len(l)<=1:
            return None
        else:
            return cDeserialize(l)

def cDeserialize(l):
    if len(l)==0:
        return None
    if l[0]!= '#':
        root=TreeNode(int(l[0]))
        l.remove(l[0])
        root.left = cDeserialize(l)
        root.right= cDeserialize(l)
    else:
        l.remove(l[0])
        root=None
    return root
看了点别人的代码，第二步都是定义一个全局变量跟踪s的第一个值。我采用了动态更新l数组的方法。当l空的时候递归截止
发表于 2019-05-02 19:11:15 回复(0)
Python
欧巴禾头像 欧巴禾
class Solution:
    def Serialize(self, root):
        # write code here
        if not root:
            return '#'
        return str(root.val) +',' + self.Serialize(root.left) +','+ self.Serialize(root.right)
    
    def Deserialize(self, s):
        list = s.split(',')
        return self.deserializeTree(list)

    def deserializeTree(self, list):
        if len(list)<=0:
            return None
        val = list.pop(0)
        root = None
        if val != '#':
            root = TreeNode(int(val))
            root.left = self.deserializeTree(list)
            root.right = self.deserializeTree(list)
        return root
发表于 2019-04-25 14:46:53 回复(0)
Python
share1722头像 share1722

序列化相对比较简单 节点值加上左子树 右子树 递归写起来比较单间
反序列化相对复杂一点 需要用递归 以124###35##6##(以#代替)
(1)1是根节点
(2)接下来2是1的左子树 4是2的左子树
(3)接下来两个## 说明4是叶子节点
(4)# 说明2右子树是null
(5)接下来构建根节点的右子树
...
代码如下：

class Solution:
    def Serialize(self, root):
        if root is None:
            return '$'
        else:
            return str(root.val) + ',' + self.Serialize(root.left) + ',' + self.Serialize(root.right)

    def createTree(self, ss, index):
        if ss[index] == '$':
            return None, index + 1
        root = TreeNode(int(ss[index]))
        index += 1
        root.left, index = self.createTree(ss, index)
        root.right, index = self.createTree(ss, index)
        return root, index

    def Deserialize(self, s):
        ss = s.split(',')
        return self.createTree(ss, 0)[0]
发表于 2019-03-21 22:15:55 回复(0)
Python
味次酱头像 味次酱

Python
序列化：把内存的代码，持久化成字符串
反序列化：把字符串，变成内存对象
解题思路：
树的序列化：先序遍历， “#” 表示占位，当前的值加上下划线 “_”

树的反序列化：利用闭包的特性，加上队列弹出的优点 使用Python实现很优雅，很happy

class Solution:
    def Serialize(self, root):
        if not root:
            return '#'
        res = str(root.val)
        res += '_' + self.Serialize(root.left)
        res += '_' + self.Serialize(root.right)
        return res
        # write code here
    def Deserialize(self, s):
        lst = s.split('_')
        def des():
            if not lst:
                return None
            v = lst.pop(0)
            if v == '#':
                return None
            else:
                head = TreeNode(int(v))
                head.left = des()
                head.right = des()
            return head
        return des()
发表于 2018-11-24 10:40:31 回复(3)
Python
牛客542767430号头像 牛客542767430号 
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def Serialize(self, root):
        # write code here
        def walkTree(root):
            if root:
                output.append(root.val)
                walkTree(root.left)
                walkTree(root.right)
            else:
                output.append(None)
        output = []
        walkTree(root)
        return output
    
    def Deserialize(self, s):
        # write code here
        def walkArray(vals):
            root = None
            val = next(vals)
            if val != None:
                root = TreeNode(val)
                root.left = walkArray(vals)
                root.right = walkArray(vals)
            return root

        return walkArray(iter(s))

发表于 2018-08-08 11:36:41 回复(0)
Python
外卖老谭头像 外卖老谭 
    def Deserialize(self, s):
        try:
            s = s.split(',')
        except:
            pass
        if len(s) == 0:
            return None
        if len(s) == 1 and s[0] != '#':
            return TreeNode(int(s[0]))
        elif len(s) == 1 and s == '#':
            return None
        else:
            self.s = s[1:]
            tree = None
            if s[0] != '#':
                tree = TreeNode(int(s[0]))
                tree.left = self.Deserialize(self.s)
                tree.right = self.Deserialize(self.s)
            return tree

发表于 2018-07-28 12:21:00 回复(0)
Python
bingoxia头像 bingoxia
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    index = -1
    def Serialize(self, root):
        # write code here
        res = []
        s = self.helper(root,res)
        return s
    def helper(self,root,res):
        if not root:
            res.append('#')
            return ','.join(res)
        res.append(str(root.val))
        self.helper(root.left,res)
        self.helper(root.right,res)
        return ','.join(res)
    
    def Deserialize(self, s):
        # write code here
        self.index = self.index + 1
        temp = s.split(',')
        if  self.index >= len(temp):
            return None
        root = None
        if temp[self.index] != '#':
            root = TreeNode(int(temp[self.index]))
            root.left = self.Deserialize(s)
            root.right = self.Deserialize(s)
        return root
发表于 2018-05-25 15:49:58 回复(0)
提交观点

问题信息

队列 树
难度：
28条回答 112306浏览

热门推荐

通过挑战的用户

查看代码

相关试题

序列化二叉树

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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