首页 > 试题广场 >

序列化二叉树

[编程题]序列化二叉树
  • 热度指数：486272 时间限制：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，点此查看相关信息
算法知识视频讲解
添加回答
Ron头像 Ron 
 public class Solution {
    public int index = -1;
    String Serialize(TreeNode root) {
       StringBuilder s = new StringBuilder();
        if(root == null){
            s.append("#,");
            return s.toString();
        }
        s.append(root.val+",");
        s.append(Serialize(root.left));
        s.append(Serialize(root.right));
        return s.toString();
  }
    TreeNode Deserialize(String str) {
       index++;
        int len = str.length();
        if(index >= len){
            return null;
        }
        String[] DLRseq = str.split(",");
        TreeNode leave = null;
        if(!DLRseq[index].equals("#")){
            leave = new TreeNode(Integer.valueOf(DLRseq[index]));
            leave.left = Deserialize(str);
            leave.right = Deserialize(str);
        }
        return leave;
  }
}

编辑于 2015-08-10 15:14:42 回复(1)
Ctrlturtle头像 Ctrlturtle 
class Solution {
public:
    
    void serializeHelper(TreeNode *root,string &str){//按先序DFS序列化
        if(root==NULL){
            str+="#,";
            return ;
        }
        str+=to_string(root->val);
        str+=',';
        serializeHelper(root->left,str);
        serializeHelper(root->right,str);
    }
    TreeNode* deserializeHelper(string &str){//反序列化
        if(str.empty())return NULL;
        if(str[0]=='#'){//当前字符对应空结点，跳过
            str=str.substr(2);//跳过当前'#'和','开始截取
            return NULL;//返回空子树
        }
        TreeNode *pRoot=new TreeNode(stoi(str));//stoi:string转int，后面出现逗号被截断，只转换当前数字字符
        str=str.substr(str.find_first_of(',')+1);//跳过下一个逗号截取
        pRoot->left=deserializeHelper(str);//重建左子树
        pRoot->right=deserializeHelper(str);//重建右子树
        return pRoot;
    }
    
    char* Serialize(TreeNode *root) {    
         if(root==NULL)return NULL;
         string str("");
         serializeHelper(root,str);
         char* res=new char[str.size()+1];
         strcpy(res,str.c_str());
         return res;
    }
    TreeNode* Deserialize(char *str) {
    	if(str==NULL)return NULL;
        string s(str);
        return deserializeHelper(s);
    }
    
};

发表于 2017-06-17 17:07:44 回复(0)
Python
zxlly要offer头像 zxlly要offer 
'''
解法：
序列化的部分，按行，如果为空的，就用'.'代替，最后序列化的结果用一个list保存
反序列化部分，递归，增加一个idx变量，指示位置
'''
class Solution:
    def Serialize(self, root):
        # write code here
        if root == None:
            # return "."
            return ["."]
        nodes_list = [[root]]
        result = []
        while nodes_list:
            current_nodes = nodes_list[0]
            nodes_list = nodes_list[1:]
            new_nodes = []
            flag = False
            # 如果当前层的节点全是None，那就结束，返回
            for node in current_nodes:
                if node != None:
                    flag = True
                    break
            if flag != True:
                return result
            while current_nodes:
                if current_nodes[0] != None:
                    result.append(current_nodes[0].val)
                    new_nodes.append(current_nodes[0].left)
                    new_nodes.append(current_nodes[0].right)
                else:
                    result.append(".")
                    new_nodes.append(None)
                    new_nodes.append(None)
                current_nodes = current_nodes[1:]
            if new_nodes:
                nodes_list.append(new_nodes)
        return result

    def Deserialize(self, s, idx=0):
        if idx >= len(s):
            return None
        if s[idx] == '.':
            return None
        root = TreeNode(int(s[idx]))
        root.left = self.Deserialize(s, idx*2+1)
        root.right = self.Deserialize(s, idx*2+2)
        return root
发表于 2018-05-20 17:09:55 回复(0)
夜小楼Dream头像 夜小楼Dream 
#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):
        self.s = ''
        self.sarializeCore(root)
        return self.s

    def sarializeCore(self,root):
        if root is None:
            self.s += "#,"
            return
        self.s += str(root.val)+","
        self.sarializeCore(root.left)
        self.sarializeCore(root.right)

    def Deserialize(self, s):
        if s is None:
            return None
        if len(s)==1 and s[0]=="#":
            return None
        self.index = 0
        s= s.split(',')
        root = self.DeserializeCore(s)
        return root

    def DeserializeCore(self,s):

        t = s[self.index]
        if t.isdigit():
            root = TreeNode(int(t))
            self.index +=1
            left = self.DeserializeCore(s)
            right = self.DeserializeCore(s)
            root.left = left
            root.right = right
            return root
        elif t =="#":
            self.index+=1
            return None

t = TreeNode(8)
t1 =TreeNode(6)
t2 = TreeNode(10)
t3 = TreeNode(5)
t4 =TreeNode(7)
t5 = TreeNode(9)
t6 = TreeNode(11)
t.left = t1
t.right = t2
t1.left = t3
t1.right = t4
t2.left = t5
t2.right = t6
print Solution().Serialize(t)
print Solution().Deserialize(Solution().Serialize(t))


发表于 2016-12-09 11:30:16 回复(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)
Java
惠灵顿靖头像 惠灵顿靖 
public class Solution {
        public String Serialize(TreeNode root) {
        if(root == null) return "{}";
        StringBuilder res = new StringBuilder("{");
        Queue<TreeNode> queue = new LinkedList<TreeNode>() {{ add(root); }};
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if(node != null) {
                res.append(node.val + ",");
                queue.add(node.left);
                queue.add(node.right);
            }
            else res.append("null,");
        }
        res.deleteCharAt(res.length() - 1);
        res.append("}");
        return res.toString();
    }

    public TreeNode Deserialize(String data) {
        if(data.equals("{}")) return null;
        String[] vals = data.substring(1, data.length() - 1).split(",");
        TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int i = 1;
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if(!vals[i].equals("null")) {
                node.left = new TreeNode(Integer.parseInt(vals[i]));
                queue.add(node.left);
            }
            i++;
            if(!vals[i].equals("null")) {
                node.right = new TreeNode(Integer.parseInt(vals[i]));
                queue.add(node.right);
            }
            i++;
        }
        return root;
    }

发表于 2021-07-15 20:14:09 回复(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)
小松nino头像 小松nino 
class Solution {
public:
    char* Serialize(TreeNode *root) {  
        string res;
        TreeNode* p=root;
        stack<TreeNode*> s;
        while(!s.empty()||p!=NULL){
            while(p!=NULL){
                res+=to_string(p->val)+"!";
                s.push(p);
                p=p->left;
            }
            res+="#!";
            p=s.top();
            s.pop();
            p=p->right;
        }
        res+="#!";
        char *str=new char[res.length()+1];
       	strcpy(str,res.c_str());
        return str;
    }
    TreeNode* Deserialize(char *&str) {
    	TreeNode* p=NULL;
        int num=0;
        if(str[0]=='#'){
            str=str+2;
            return NULL;
        }
        while(*str!='!'){
            num=num*10+(*str-'0');
            str++;
        }
        str++;
        p=new TreeNode(num);
        p->left=Deserialize(str);
        p->right=Deserialize(str);
        return p;
    }
};

发表于 2017-06-01 17:55:19 回复(0)
fuyufjh头像 fuyufjh
充分利用STL里的stringstream 

class Solution {
	void dfs(TreeNode *node, stringstream &out)
	{
		if (!node) {
			out << "#" << endl;
			return;
		}
		out << node->val << endl;
		dfs(node->left, out);
		dfs(node->right, out);
	}
	bool getNumber(stringstream &in, int &number) {
		char buf[20];
		in >> buf;
		if (buf[0] == '#') return false;
		number = atoi(buf);
		return true;
	}
	TreeNode* construct(stringstream &in) {
		int val;
		if (getNumber(in, val)) {
			TreeNode *node = new TreeNode(val);
			node->left = construct(in);
			node->right = construct(in);
			return node;
		}
		return NULL;
	}
public:
	char* Serialize(TreeNode *root) {
		stringstream ss;
		dfs(root, ss);
		const char *c_str = ss.str().c_str();
		char *serial = new char[ss.str().length() + 1];
		strcpy(serial, c_str);
		return serial;
	}
	TreeNode* Deserialize(char *c_str) {
		if (!c_str) return NULL;
		string str(c_str);
		stringstream ss(str);
		return construct(ss);
	}
};

发表于 2015-07-29 22:54:49 回复(0)
一直奔跑的蜗牛头像 一直奔跑的蜗牛 
先序遍历二叉树，空节点使用“#”表示
public class Solution {
    int index;
	String Serialize(TreeNode root) {
		StringBuilder sb = new StringBuilder();
		if (root == null) {
			sb.append("#,");
			return sb.toString();
		}
		sb.append(root.val + ",");
		sb.append(Serialize(root.left));
		sb.append(Serialize(root.right));
		return sb.toString();
	}

	TreeNode Deserialize(String str) {
		if (str == null)
			return null;
                index=-1;
		String[] DLRseq = str.split(",");
		return DeserializeDLR(DLRseq);
	}
	TreeNode DeserializeDLR(String[] DLRseq) {
		index++;
		TreeNode leave = null;
		System.out.println(index);
		if (!DLRseq[index].equals("#")) {
			leave = new TreeNode(Integer.valueOf(DLRseq[index]));
			leave.left = DeserializeDLR(DLRseq);
			leave.right = DeserializeDLR(DLRseq);
		}
		return leave;
	}
}

发表于 2016-06-23 11:07:35 回复(4)
Python
刘东荣头像 刘东荣
看到好多都在投机取巧 
#序列化：前序遍历，左子树右子树之前加当前深度作为分隔，同时对该深度值进行转义，
#      转义编码方式：如果找到depth或depth-1则在前面加入depth-1进行转义
#反序列化：取第一个数为根，从左往右找depth，如果找到depth-1转义字符，则跳过一个,
#        左右子树解码递归
class Solution:
    def Serialize(self, root,depth = 0):
        if root is None:return []
        s = [root.val]
        s.extend(self.encode(self.Serialize(root.left,depth+1),depth))
        s.append(depth)
        s.extend(self.encode(self.Serialize(root.right,depth+1),depth))
        print s,depth
        return s
    def encode(self,s,depth):
        res = []
        for i in s:
            if i == depth or i == depth-1:
                res.append(depth-1)
            res.append(i)
        return res
    
    def Deserialize(self, s,depth = 0):
        if len(s) == 0:return None
        print s,depth
        root = TreeNode(s[0])
        i = 1
        while i < len(s):
            if s[i] == depth-1:i+=1
            elif s[i] == depth:
                root.left = self.Deserialize(self.decode(s[1:i],depth),depth+1)
                root.right = self.Deserialize(self.decode(s[i+1:],depth),depth+1)
                break
            i+=1
        return root

    def decode(self, s,depth):
        res = []
        i = 0
        while i<len(s):
            if s[i] == depth-1:
                i+=1
            res.append(s[i])
            i+=1
        return res

发表于 2018-01-23 23:38:44 回复(0)
daemon4u头像 daemon4u 
//思路：我们知道，通过一棵二叉树的前序遍历序列和中序遍历序列可以还原一棵树，所以此题如果使用这种方式则明显可解。只是问题在于，在反序列化
//的时候需要全部读出序列化串后才能还原。

//于是我们可以采用层次遍历的方式序列化一棵树，在节点为null的时候使用#作为占位，因为反序列化的时候需要使用串的索引来确定父节点的子节点，
//也就是说我们需要将一棵树序列化成一棵完全二叉树，空节点使用#作为占位。

public class Serialize {
	String Serialize(TreeNode root) {
        if(root == null){
        	return null;
        }
        StringBuffer sb = new StringBuffer();
        ArrayList<TreeNode> list = new ArrayList<TreeNode>();
        int count = (1 << treeDepth(root)) - 1;//计数，拿到此树的深度后计算对应完全二叉树节点数
        list.add(root);
        count--;
        TreeNode tmpNode = null;
        
        //层次遍历二叉树，开始序列化
        while(list.size() > 0 && count >= 0){
        	tmpNode = list.remove(0);
        	if(tmpNode != null){
        		sb.append(tmpNode.val+",");
        		list.add(tmpNode.left);
        		list.add(tmpNode.right);
        	}else{
        		sb.append("#,");//#作为空节点占位符
        		list.add(null);
        		list.add(null);
        	}
        	count --;
        }
        return sb.toString();
    }

    TreeNode Deserialize(String str) {
    	if(str == null || str.length() == 0){
    		return null;
    	}
    	return Deserialize(str.split(","), 0);
    }

    TreeNode Deserialize(String[] strings, int index){
        
    	TreeNode newNode = null;
    	if(index < strings.length){
    		if(!strings[index].equals("#")){
    			newNode = new TreeNode(Integer.parseInt(strings[index]));
    			newNode.left = Deserialize(strings, 2 * index + 1);
    			newNode.right = Deserialize(strings, 2 * index + 2);
    		}
    	}
    	return newNode;
    }
    
    int treeDepth(TreeNode root){
    	int depth = 0;
    	if(root == null){
    		return depth;
    	}else{
    		int lDepth = treeDepth(root.left) + 1;
    		int rDepth = treeDepth(root.right) + 1;
    		return lDepth > rDepth ? lDepth : rDepth;
    	}
    }
}

发表于 2016-04-22 20:15:56 回复(1)
Python 3
愣头青丶别处仰望头像 愣头青丶别处仰望
# 1 使用中序遍历来序列化（如果空节点比较多，层次遍历的存储比较浪费空间），也使用中序遍历过程来反序列化，保证序列化和反序列化的统一
# 2 整体框架使用递归来中序遍历
# 3 代码 
class Solution:
    s = []
    def SerializeFunction(self, root): # 中序遍历来序列化
        if not root:
            self.s.append('#')
            return
        self.s.append(root.val)
        self.SerializeFunction(root.left)
        self.SerializeFunction(root.right)
    def Serialize(self, root:TreeNode):
        if not root:
            self.s = ['#']
        self.s = []
        self.SerializeFunction(root)
        return self.s
    # 反序列化就是使用中序遍历结果来构建二叉树的过程
    def DeserializeeFunction(self, root, vals): 
        if len(vals) == 0:
            return None
        if vals[0] != '#':
            root = TreeNode(vals[0])
            vals.pop(0)
            root.left = self.DeserializeeFunction(root.left,vals)
            root.right = self.DeserializeeFunction(root.right,vals)
            return root
        else:
            root = None
            vals.pop(0)
            return root
    def Deserialize(self, vals):
        root =  None
        return self.DeserializeeFunction(root, vals)


发表于 2022-08-10 00:06:44 回复(0)
Javascript
哲学家L头像 哲学家L 
function Serialize(root)
{
    return JSON.stringify(root)
}
function Deserialize(s)
{
    return JSON.parse(s)
}


发表于 2022-07-29 10:53:01 回复(2)
C++
大耳贼重燃复国斗志头像 大耳贼重燃复国斗志
1、使用前需遍历思想实现 
class Solution {
public:
    void serdsf(TreeNode *root,string& res)
    {
        if(root==nullptr)
        {
            res.push_back('#');
            res.push_back(',');
            return;
        }
        res+=(to_string(root->val));
        res.push_back(',');
        serdsf(root->left,res);
        serdsf(root->right,res);
    }
    char* Serialize(TreeNode *root) {  
        if(root==nullptr)
            return nullptr;
        string res="";
        serdsf(root,res);
        char *ret = new char[res.length() + 1];
        strcpy(ret, res.c_str());
        return ret;
    }
    TreeNode* deserdfs(queue<string>& q)
    {
        if(q.empty())    return nullptr;
        
        string tem=q.front();
        q.pop();
        if(tem=="#")
            return nullptr;
        TreeNode* head=new TreeNode(atoi(tem.c_str()));
        head->left=deserdfs(q);
        head->right=deserdfs(q);
        
        return head;
    }
    TreeNode* Deserialize(char *str){
        if(str==nullptr)    return nullptr;
        string tem=str;
        queue<string> q;
        while(1)
        {
            int index=tem.find_first_of(',');
            if(index>=tem.size())
                break;
            q.push(tem.substr(0,index));
            tem=tem.substr(index+1);
        }
        return deserdfs(q);
    }
};


发表于 2022-07-20 23:06:25 回复(0)
Java
lizi-hust头像 lizi-hust 
import java.util.*;
public class Solution {
    String Serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        dfs(root, sb);
        return new String(sb.substring(0, sb.length()-1));
    }
    
    public void dfs(TreeNode root, StringBuilder sb){
        if(root==null) {
            sb.append("#").append(",");
            return;
        }
        sb.append(root.val).append(",");
        dfs(root.left, sb);
        dfs(root.right, sb);
    }
    
    TreeNode Deserialize(String str) {
        String[] strs = str.split(",");
        LinkedList<String> list = new LinkedList<>();
        for(int i=0; i<strs.length; i++) list.add(strs[i]);
        
        return dfs(list);
    }
    
    public TreeNode dfs(LinkedList<String> list){
        String str = list.removeFirst();
        if(str.equals("#")) return null;
        
        TreeNode root = new TreeNode(Integer.parseInt(str));
        root.left = dfs(list);
        root.right = dfs(list);
        return root;
    }
}

发表于 2022-07-19 16:00:12 回复(0)
Java
ITwolffy头像 ITwolffy 
public class Solution {
    String Serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        serialize(root, sb);
        return sb.toString();
    }
    void serialize(TreeNode root, StringBuilder sb) {
        if (root == null) {
            sb.append("#,");
            return;
        }
        
        sb.append(root.val).append(",");
        serialize(root.left, sb);
        serialize(root.right, sb);
    }
    TreeNode Deserialize(String str) {
        String[] nums = str.split(",");
        int[] i = {0};
        return deserialize(nums, i);
    }
    TreeNode deserialize(String[] nums, int[] i) {
        String s = nums[i[0]];
        i[0]++;
        if (s.equals("#")) {
            return null;
        }
        TreeNode root = new TreeNode(Integer.parseInt(s));
        root.left = deserialize(nums, i);
        root.right = deserialize(nums, i);
        return root;
    }
}

发表于 2022-06-22 13:13:16 回复(0)
但我也喜欢烟花呀头像 但我也喜欢烟花呀
string多好用啊。。。char*。。认真的吗。
发表于 2022-05-20 17:39:06 回复(0)
积极健康向上的少年头像 积极健康向上的少年
c++的为啥返回是cha*，不直接用string呢。。。
发表于 2022-04-05 13:23:53 回复(0)
Java
李橙子头像 李橙子
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    public int index = -1;
    String Serialize(TreeNode root) {
        StringBuffer sb = new StringBuffer();
        if(root == null){
            sb.append("#,");
            return sb.toString();
        }
        sb.append(root.val + ",");
        sb.append(Serialize(root.left));
        sb.append(Serialize(root.right));
        return sb.toString();
  }
    TreeNode Deserialize(String str) {
        index++;
       int len = str.length();
        if(index >= len){
            return null;
        }
        String[] strr = str.split(",");
        TreeNode node = null;
        if(!strr[index].equals("#")){
            node = new TreeNode(Integer.valueOf(strr[index]));
            node.left = Deserialize(str);
            node.right = Deserialize(str);
        }
         
        return node;
  }
}
发表于 2022-02-10 15:57:00 回复(0)
提交观点

问题信息

队列 树
难度：
629条回答 112258浏览

热门推荐

通过挑战的用户

查看代码

相关试题

序列化二叉树

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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