首页 > 试题广场 >

序列化二叉树

[编程题]序列化二叉树
  • 热度指数:477823 时间限制: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,点此查看相关信息
我这边再来一个层序遍历的序列化方式把,其实层序感觉还是蛮简单的,只需要把节点放入一个双向队列里面去存起来就ok了。代码如下:
import java.util.*;
public class Solution {
    String Serialize(TreeNode root) {
        if(root == null){
            return "#!";
        }
        String res = "";
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode cur = queue.poll();
            if(cur!=null){
                res+=cur.val+"!";
                queue.offer(cur.left);
                queue.offer(cur.right);
            }else{
                res+="#!";
            }
        }
        return res;
    }
    
    TreeNode Deserialize(String str) {
        if("#!".equals(str))return null;
       String[] res = str.split("!");
       int index = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode head = generateTreeNode(res[index++]);
        queue.offer(head);
        while(!queue.isEmpty()){
            TreeNode temp = queue.poll();
            temp.left = generateTreeNode(res[index++]);
            temp.right = generateTreeNode(res[index++]);
            if(temp.left!=null)queue.offer(temp.left);
            if(temp.right!=null)queue.offer(temp.right);
        }
        return head;
    }
    TreeNode generateTreeNode(String val){
        if("#".equals(val)){
            return null;
        }
        return new TreeNode(Integer.valueOf(val));
    }
}

再来一个前序遍历的版本,个人感觉前序遍历的版本其实更加的简单了,代码如下:
import java.util.*;
public class Solution {
    //前序遍历序列化二叉树
    String Serialize(TreeNode root) {
        if(root == null){
            return "#!";
        }
        String res = root.val+"!";
        res+=Serialize(root.left);
        res+=Serialize(root.right);
        return res;
    }
    //前序遍历反序列化二叉树
    TreeNode Deserialize(String str) {
        //空树直接返回null
        if("#!".equals(str))return null;
        //获取序列化的queue
        Queue<String> queue = getQueue(str);
        //调用反序列化的函数
        return serializeHelper(queue);
        //return head;
    }
    //生成一个二叉树节点
    TreeNode generateTreeNode(String val){
        if("#".equals(val)){
            return null;
        }
        return new TreeNode(Integer.valueOf(val));
    }
    //获取队列的函数
    Queue<String> getQueue(String str){
        String[] res = str.split("!");
        int len = res.length;
        Queue<String> queue = new LinkedList<>();
        for(int i=0;i<len;i++){
            queue.offer(res[i]);
        }
        return queue;
    }
    //反序列化到底函数
    TreeNode serializeHelper(Queue<String> queue){
        String value = queue.poll();
        if("#".equals(value))return null;
        TreeNode head = generateTreeNode(value);
        head.left = serializeHelper(queue);
        head.right = serializeHelper(queue);
        return head;
    }
}


编辑于 2020-02-17 16:12:56 回复(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):
        """前序递归"""
		ret = []
		if not root:
			return '#'
		ret.append(str(root.val))
		l = self.Serialize(root.left)
		ret.append(l)
		r = self.Serialize(root.right)
		ret.append(r)
		return ','.join(ret)
    
	def Serialize_no_rec(self, root):
        """前序非递归"""
		serialize_str = []
		if not root:
			return '#'
		s = []
		while root or s:
			while root:
				# serialize_str += (str(root.val)+',')
				serialize_str.append(str(root.val))
				s.append(root.right)  # 栈中存放右结点,便于左子树访问完之后回溯
				root = root.left
			# serialize_str += "#,"
			serialize_str.append('#')  # 左结点访问完,用#来标识该结点的空指针
			root = s.pop()  # 依次访问栈中的右子树  # print serialize_str
		return ','.join(serialize_str)



	# write code here

	def Deserialize(self, s):
		serialize = s.split(',')
		tree, sp = self.deserialize(serialize, 0)
		return tree

	def deserialize(self, s, sp):
		if sp >= len(s) or s[sp] == "#":
			return None, sp + 1
		node = TreeNode(int(s[sp]))
		sp += 1
		node.left, sp = self.deserialize(s, sp)
		node.right, sp = self.deserialize(s, sp)
		return node, sp

	# write code here

编辑于 2016-08-23 09:54:04 回复(0)
用递归实现:
序列化二叉树,按照中序遍历二叉树的顺序,先左节点,后右节点,当到‘#’时
候,说明左节点或者右节点为NULL,同样反序列二叉树也一个道理,需要注意的
是在序列和反序列二叉树的时候,注意字符串与整数的转换,一般字符串转换为
整数,用迭代循环实现,整数转换为字符串可以用sprintf实现或者itoa实现

实现代码如下:

class Solution {
public:
    char* Serialize(TreeNode *root) {    
        if(root==NULL)
			return NULL;
		string str;
		Serialize1(root,str);
		return const_cast<char*>(str.c_str());
    }
    TreeNode* Deserialize(char *str) {
		if(str==NULL||*str=='\0')
			return NULL;
		int num=0;
		return Deserialize1(str,num);
    }
	void Serialize1(TreeNode *root,string &str)
	{
		if(root==NULL)
		{
			str+="#,";
			return ;
		}
		char ch[10];
		sprintf(ch,"%d",root->val);
		str+=ch;
		str+=",";
		Serialize1(root->left,str);
		Serialize1(root->right,str);
	}
	TreeNode* Deserialize1(char *str,int &num)
	{
		int val=0;
		if(str[num]=='#')
		{
			num+=2;
			return NULL;
		}
		while(str[num]!=','&&str[num]!='\0')
		{
			val=val*10+str[num]-'0';
			num++;
		}
		num++;
		TreeNode *root=new TreeNode(val);
		root->left=Deserialize1(str,num);
		root->right=Deserialize1(str,num);
		return root;
	}
};

编辑于 2015-09-02 17:25:12 回复(12)
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

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

    }

}
*/
import java.util.*;
public class Solution {
    String Serialize(TreeNode root) {
       if(root == null)
       {
           return "#,";
       }
       String res = root.val + ",";
       res += Serialize(root.left);
      res += Serialize(root.right);
      return res;
        
  }
    TreeNode Deserialize(String str) {
       String[] values = str.split(",");
        Queue<String> queue= new LinkedList<String>();
        for(int i = 0;i != values.length; i ++)
         {
            queue.offer(values[i]);
        }
        return preOrder(queue);
  }
    public TreeNode preOrder(Queue<String> queue)
    {
        String value = queue.poll();
        if(value.equals("#"))
         {
            return null;
        }
        TreeNode head = new TreeNode(Integer.valueOf(value));
        head.left = preOrder(queue);
        head.right = preOrder(queue);
        return head;
    }
}

发表于 2016-08-15 22:16:16 回复(1)
 层序实现,代码略长。 
如        10 
        20      30 
    4    #      #   5 
6   #               7 # 
先得到层序序列 10,20,30,4,#,#,5,6,#,#,#,#,#,7,#, 
然后按照 i 的左节点为i*2+1 ,右节点为 i*2+2 的规律恢复就行了   

      string Print(TreeNode* pRoot) { 
        string ans; 
        if(pRoot==NULL) return ans; 
                 queue<TreeNode*> que; 
             que.push(pRoot); 
        string cc; 
        while(1){ 
            queue<TreeNode*> tmp; 
            int token=0; 
            while(!que.empty()) 
            { 
                string pp = "#,"; 
                if( que.front()!=NULL) {stringstream u;  u<<que.front()->val; cc+= u.str() + ','; } 
                else cc+= pp; 
                 
                if(que.front())  {tmp.push (que.front()->left);token=1;} 
                  else tmp.push(NULL); 
                 
                if(que.front())  {tmp.push(que.front()->right);token=1;} 
                  else tmp.push(NULL); 
                que.pop(); 
            } 
            if(token==0) return ans; 
            if (cc.size()!=0) { 
                ans+=cc; 
                cc.clear(); 
            } 
            while (!tmp.empty()) { 
                que.push(tmp.front()); 
                tmp.pop(); 
            } 
        } 
    } 
    char ss[500]; 
    char* Serialize(TreeNode *root) {     
        string s= Print(root); 
        return strcpy(ss, s.c_str()); 
    } 
    vector<TreeNode*> p; 
    TreeNode* Deserialize(char *str) { 
        string sss=str; 
        TreeNode* root; 
         if (sss.size() == 0) { 
            return NULL; 
        } 
        vector<string > tt; 
        for (int i=0; i<sss.size(); ) { 
            string tmp=""; 
            while (i<sss.size() && sss[i]!=',' ) { 
                tmp+=sss[i]; 
                i++; 
            } 
            i++; 
            if(tmp.size())tt.push_back(tmp); 
        } 
         
        for (int i=0; i<tt.size(); i++) { 
            if (tt[i]=="#") { 
                p.push_back(NULL); 
            } 
            else{ 
                stringstream u ; 
                u<<tt[i]; 
                int num ; 
                u>>num; 
                p.push_back(new TreeNode(num)); 
            } 
        } 
         
        for (int i=0; i<p.size(); i++) { 
            if (p[i] == NULL) { 
                continue; 
            } 
            if(i*2+1 < p.size()) 
            { 
                p[i]->left = p[i*2+1]; 
            } 
            if(i*2+2 < p.size()) 
            { 
                p[i]->right= p[i*2+2]; 
            } 
        } 
        return p[0]; 
    }

发表于 2016-03-12 16:26:01 回复(3)
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)
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)
'''
解法:
序列化的部分,按行,如果为空的,就用'.'代替,最后序列化的结果用一个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)

这个题目真是。。。

class Solution {
private:
    string serialize(TreeNode* root){
        if(root == nullptr){
            return "#!";
        }
        string str;
        str = to_string(root->val) + "!";
        str += serialize(root->left);
        str += serialize(root->right);
        return str;
    }

    TreeNode* deserialize(char *&str) {
        if(*str == '#'){
            str++;
            return nullptr;
        }
        int num = 0;
        while(*str != '!'){
            num = num * 10 + *str - '0';
            str++;
        }
        TreeNode* node = new TreeNode(num);
        node->left = deserialize(++str);
        node->right = deserialize(++str);
        return node;
    }
public:
    char* Serialize(TreeNode *root) {    
        string str = serialize(root);
        char* res = new char[str.size()];
        for(int i=0; i<str.size(); i++){
            res[i] = str[i];
        }
        return res;
    }

    TreeNode* Deserialize(char *str){
        return deserialize(str);
    }
};
发表于 2017-12-27 11:10:45 回复(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):
        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实现很优雅,很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)
class Solution:
    def Serialize(self, root):
        # write code here
        return root
    def Deserialize(self, s):
        # write code here
        return s
发表于 2017-10-27 09:05:33 回复(7)
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)
用的前序遍历,结果储存再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)
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)
充分利用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)
看到好多都在投机取巧
#序列化:前序遍历,左子树右子树之前加当前深度作为分隔,同时对该深度值进行转义,
#      转义编码方式:如果找到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)
//思路:我们知道,通过一棵二叉树的前序遍历序列和中序遍历序列可以还原一棵树,所以此题如果使用这种方式则明显可解。只是问题在于,在反序列化
//的时候需要全部读出序列化串后才能还原。

//于是我们可以采用层次遍历的方式序列化一棵树,在节点为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)
# 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)
function Serialize(root)
{
    return JSON.stringify(root)
}
function Deserialize(s)
{
    return JSON.parse(s)
}


发表于 2022-07-29 10:53:01 回复(2)