首页 > 试题广场 > 序列化二叉树
[编程题]序列化二叉树
  • 热度指数:341294 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
请实现两个函数,分别用来序列化和反序列化二叉树

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

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

例如,我们可以把一个只有根节点为1的二叉树序列化为"1,",然后通过自己的函数来解析回这个二叉树
其实我是不想吐槽的。。。。。

O(1)写法【误 :) 】
typedef TreeNode* pnode;
class Solution {
    pnode hehe;
public:
    char* Serialize(TreeNode *root) {    
        hehe = root;
        return "(*^_^*)";
    }
    TreeNode* Deserialize(char *str) {
    	return hehe;
    }
};

O(n)写法
typedef TreeNode node;
typedef TreeNode* pnode;
typedef int* pint;
class Solution {
    vector<int> buf;
    void dfs(pnode p){
        if(!p) buf.push_back(0x23333);
        else{
            buf.push_back(p -> val);
            dfs(p -> left);
            dfs(p -> right);
        }
    }
    pnode dfs2(pint& p){
        if(*p == 0x23333){
            ++p;
            return NULL;
        }
        pnode res = new node(*p);
        ++p;
        res -> left = dfs2(p);
        res -> right = dfs2(p);
        return res;
    }
public:
    char* Serialize(TreeNode *p) {
        buf.clear();
        dfs(p);
        int *res = new int[buf.size()];
        for(unsigned int i = 0; i < buf.size(); ++i) res[i] = buf[i];
        return (char*)res;
    }
    TreeNode* Deserialize(char *str) {
        int *p = (int*)str;
        return dfs2(p);
    }
};

编辑于 2015-12-04 12:22:26 回复(70)
# -*- 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
        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

发表于 2017-08-03 21:20:43 回复(8)
/*
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;
  }
}

发表于 2015-10-17 11:43:12 回复(56)
/*
 1. 对于序列化:使用前序遍历,递归的将二叉树的值转化为字符,并且在每次二叉树的结点
不为空时,在转化val所得的字符之后添加一个' , '作为分割。对于空节点则以 '#' 代替。
 2. 对于反序列化:按照前序顺序,递归的使用字符串中的字符创建一个二叉树(特别注意:
在递归时,递归函数的参数一定要是char ** ,这样才能保证每次递归后指向字符串的指针会
随着递归的进行而移动!!!)
*/
class Solution {   
public:
    char* Serialize(TreeNode *root) {
       if(root == NULL)
           return NULL;
        string str;
        Serialize(root, str);
        char *ret = new char[str.length() + 1];
        int i;
        for(i = 0; i < str.length(); i++){
            ret[i] = str[i];
        }
        ret[i] = '\0';
        return ret;
    }
    void Serialize(TreeNode *root, string& str){
        if(root == NULL){
            str += '#';
            return ;
        }
        string r = to_string(root->val);
        str += r;
        str += ',';
        Serialize(root->left, str);
        Serialize(root->right, str);
    }
    
    TreeNode* Deserialize(char *str) {
    	if(str == NULL)
            return NULL;
        TreeNode *ret = Deserialize(&str);

        return ret;
    }
    TreeNode* Deserialize(char **str){//由于递归时,会不断的向后读取字符串
        if(**str == '#'){  //所以一定要用**str,
            ++(*str);         //以保证得到递归后指针str指向未被读取的字符
            return NULL;
        }
        int num = 0;
        while(**str != '\0' && **str != ','){
            num = num*10 + ((**str) - '0');
            ++(*str);
        }
        TreeNode *root = new TreeNode(num);
        if(**str == '\0')
            return root;
        else
            (*str)++;
        root->left = Deserialize(str);
        root->right = Deserialize(str);
        return root;
    }
};

编辑于 2016-08-09 12:12:18 回复(26)
//采用层序遍历,不需要将转化为完全二叉树的简单方法
public class Solution {
    String Serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        if(root != null)
            queue.add(root);
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            if(node != null){
                queue.offer(node.left);
                queue.offer(node.right);
                sb.append(node.val + ",");
            }else{
                sb.append("#" + ",");
            }
        }
        if(sb.length() != 0)
            sb.deleteCharAt(sb.length()-1);
        return sb.toString();
  }
    TreeNode Deserialize(String str) {
       TreeNode head = null;
        if(str == null || str.length() == 0)
            return head;
        String[] nodes = str.split(",");
        TreeNode[] treeNodes = new TreeNode[nodes.length];
        for(int i=0; i<nodes.length; i++){
            if(!nodes[i].equals("#"))
                treeNodes[i] = new TreeNode(Integer.valueOf(nodes[i]));
        }
        for(int i=0, j=1; j<treeNodes.length; i++){
            if(treeNodes[i] != null){
                treeNodes[i].left = treeNodes[j++];
                treeNodes[i].right = treeNodes[j++];
            }
        }
        return treeNodes[0];
  }
} 

//前序遍历
public class Solution {
    String Serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        getSerializeString(root, sb);
        if(sb.length() != 0)
            sb.deleteCharAt(sb.length()-1);
        return sb.toString();
      }
    getSerializeString(TreeNode root, StringBuilder sb){
        if(root == null)
            sb.append("#,");
        else{
            sb.append(root.val + ",");
            getSerializeString(root.left, sb);
            getSerializeString(root.right, sb);
        }
    }
    TreeNode Deserialize(String str) {
       if(str == null || str.length() == 0 || str.length() ==1)
            return null;
        String[] nodes = str.split(",");
        TreeNode[] treeNodes = new TreeNode[nodes.length];
        for(int i=0; i<nodes.length; i++){
            if(!nodes[i].equals("#"))
                treeNodes[i] = new TreeNode(Integer.valueOf(nodes[i]));
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(treeNodes[0]);
        int i = 1;
        while(treeNodes[i] != null){
            stack.peek().left = treeNodes[i];
            stack.push(treeNodes[i++]);
        }
        while(!stack.isEmpty()){
            stack.pop().right = treeNodes[++i];
            if(treeNodes[i] != null){
                stack.push(treeNodes[i++]);
                while(treeNodes[i] != null){
                    stack.peek().left = treeNodes[i];
                    stack.push(treeNodes[i++]);
                }
            }
        }
        return treeNodes[0];
      }
}

编辑于 2017-09-30 20:51:46 回复(11)
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

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

    }

}
*/
/*
	算法思想:根据前序遍历规则完成序列化与反序列化。所谓序列化指的是遍历二叉树为字符串;所谓反序列化指的是依据字符串重新构造成二叉树。
    依据前序遍历序列来序列化二叉树,因为前序遍历序列是从根结点开始的。当在遍历二叉树时碰到Null指针时,这些Null指针被序列化为一个特殊的字符“#”。
    另外,结点之间的数值用逗号隔开。
*/
public class Solution {
    int index = -1;   //计数变量
 
    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) {
    	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;
  }
}

发表于 2017-02-24 09:40:22 回复(37)
1. 存储数的前序遍历,NULL的地方填充特殊字符
class Solution {
public:
	void serializeHelper(TreeNode *node, string& s)
	{
		if (node == NULL)
		{
			s.push_back('N');
			s.push_back(',');
			return;
		}
		s += to_string(node->val);
		s.push_back(',');
		serializeHelper(node->left, s);
		serializeHelper(node->right, s);
	}
	char* Serialize(TreeNode *root)
	{
		if (root == NULL)
			return NULL;
		string s = "";
		serializeHelper(root, s);

		char *ret = new char[s.length() + 1];
		strcpy(ret, s.c_str());
		return ret;
	}
	
	TreeNode *deserializeHelper(string &s)
	{
		if (s.empty()) 
			return NULL;
		if (s[0] == 'N')
		{
			s = s.substr(2);
			return NULL;
		}
		TreeNode *ret = new TreeNode(stoi(s));
		s = s.substr(s.find_first_of(',') + 1);
		ret->left = deserializeHelper(s);
		ret->right = deserializeHelper(s);
		return ret;
	}
	
	TreeNode* Deserialize(char *str) 
	{
		if (str == NULL)
			return NULL;
		string s(str);
		return deserializeHelper(s);
	}
};
使用stringstream
class Solution {
public:	
	string sHelper(TreeNode *node)
	{
		if (node == NULL)
			return "N";
		return to_string(node->val) + "," +
				sHelper(node->left) + "," +
				sHelper(node->right);
	}

	char* Serialize(TreeNode *root) 
	{
		string s = sHelper(root);
		char *ret = new char[s.length() + 1];
		strcpy(ret, const_cast<char*>(s.c_str()));
		return ret;
	}


	TreeNode *dHelper(stringstream &ss)
	{
		string str;
		getline(ss, str, ',');
		if (str == "N")
			return NULL;
		else
		{
			TreeNode *node = new TreeNode(stoi(str));
			node->left = dHelper(ss);
			node->right = dHelper(ss);
			return node;
		}
	}

	TreeNode* Deserialize(char *str) {
		stringstream ss(str);
		return dHelper(ss);
	}
};


2. BFS,NULL填充特殊字符
未通过
class Solution {
public:

	char* Serialize(TreeNode *root) 
	{
		string s;
		queue<TreeNode*> qt;
		qt.push(root);
	
		while (!qt.empty())
		{
			TreeNode *node = qt.front();
			qt.pop();
			if (node == NULL)
			{
				s.push_back('N');
				s.push_back(',');
				continue;
			}
			s += to_string(node->val);
			s.push_back(',');
			qt.push(node->left);
			qt.push(node->right);
	
		}
		char *ret = new char[s.length() + 1];
		strcpy(ret, s.c_str());
		return ret;
	}
	TreeNode* Deserialize(char *str) 
	{
		if (str == NULL)
			return NULL;
	
		string s(str);
	
		queue<TreeNode*> nodes;
		TreeNode *ret = new TreeNode(stoi(s));
		s = s.substr(s.find_first_of(',') + 1);
		nodes.push(ret);
		while (!nodes.empty() && !s.empty())
		{
			TreeNode *node = nodes.front();
			nodes.pop();
			if (s[0] == 'N')
			{
				node->left = NULL;
				s = s.substr(2);
			}
			else
			{
				node->left = new TreeNode(stoi(s));
				nodes.push(node->left);
				s = s.substr(s.find_first_of(',') + 1);
			}
	
			if (s[0] == 'N')
			{
				node->right = NULL;
				s = s.substr(2);
			}
			else
			{
				node->right = new TreeNode(stoi(s));
				nodes.push(node->right);
				s = s.substr(s.find_first_of(',') + 1);
			}
		}
		return ret;
	}
};

编辑于 2017-01-26 02:38:00 回复(3)
分享一个LeetCode用的序列化法
class Solution {
public:
	char* Serialize(TreeNode *pRoot) {
		string s;
		if (!pRoot)
			return NULL;
		deque<TreeNode*> q;
		q.push_back(pRoot);
		while (!q.empty()) {
			int n = q.size();
			for (int i = 0; i < n; ++i) {
				if (q.front()) {
					q.push_back(q.front()->left);
					q.push_back(q.front()->right);
					s += to_string(q.front()->val) + ' ';
				} else {
					s += "# ";
				}
				q.pop_front();
			}
		}
		char* chr = strdup(s.c_str());
		return  chr;
	}
	TreeNode* Deserialize(char *str) {
		if (!str)
			return nullptr;
		int k = 0;
		auto ret = nextNode(str, k);
		deque<TreeNode*> q;
		q.push_back(ret);
		while (!q.empty()) {
			int n = q.size();
			for (int i = 0; i < n; ++i) {				
				q.front()->left = nextNode(str, k);
				q.front()->right = nextNode(str, k);
				if (q.front()->left)
					q.push_back(q.front()->left);
				if (q.front()->right)
					q.push_back(q.front()->right);
				q.pop_front();
			}
		}
		return ret;
	}
	TreeNode* nextNode(char *str,int &i) {
		string s;
		while (str[i] != '\0'&&str[i] != ' ') {
			if (str[i] == '#') {
				i += 2;
				return nullptr;
			}
			s += str[i];
			i++;
		}
		if (str[i] == ' ')
			i++;
		if (!s.empty())
			return new TreeNode(stoi(s));
		return nullptr;
	}
};

发表于 2016-07-18 14:21:03 回复(5)
这题我不知道为什么有人用vector的还有人点赞,既然题目让你用char *,就老老实实写递归就好了

class Solution {
private:
	TreeNode* decode(char *&str) {
		if(*str=='#'){
			str++;
			return NULL;
		}
		int num = 0;
		while(*str != ',')
			num = num*10 + (*(str++)-'0');
		str++;
		TreeNode *root = new TreeNode(num);
		root->left = decode(str);
		root->right = decode(str);
		return root;
    }
public:
    char* Serialize(TreeNode *root) {    
       	if(!root) return "#";
        string r = to_string(root->val);
        r.push_back(',');
        char *left = Serialize(root->left);
        char *right = Serialize(root->right);
        char *ret = new char[strlen(left) + strlen(right) + r.size()];
		strcpy(ret, r.c_str());
        strcat(ret, left);
        strcat(ret, right);
        return ret;
    }
    TreeNode* Deserialize(char *str) {
		return decode(str);
    }
};

发表于 2015-10-19 11:39:19 回复(22)
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

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

    }

}
*/
public class Solution {
    /**
    1.序列化是指通过前序遍历把二叉树变成数组
    2.反序列化是指重建二叉树
    
    */
    //前序遍历序列化,null序列化为‘#’,index 为全局变量
    int index;
    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) {
       
        //先判空
        if(str == null){
            return null;
        }
        index = -1;
        String[] strSeg = str.split(",");
        
        return DeserializeStr(strSeg);
        
  }
    
    public TreeNode DeserializeStr(String[] strSeg){
        
        index++;
        TreeNode treeNode = null;
        //字符串比较大小:== 不仅内容相同,引用地址也要相同(String类是不变类)! .equals(""):内容相同即可
        if(!strSeg[index].equals("#")){
            //新建此结点,字符串和包装类的转换
           	treeNode = new TreeNode(Integer.valueOf(strSeg[index]));
            treeNode.left = DeserializeStr(strSeg);
            treeNode.right = DeserializeStr(strSeg);
        }
        
        return treeNode;
    }
    
}



发表于 2016-12-17 11:41:19 回复(1)
我觉得这题应该写个测试用例,别人才会好理解一些
发表于 2018-05-10 15:49:39 回复(4)
# -*- 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 Solution {
    /**
     * 前序遍历序列化
     * 每个结点用"_"分割开,空结点用"#"表示
     */
    String Serialize(TreeNode root) {
        if (root == null) {
            return "#_";
        }
        String res = root.val + "_";
        res += Serialize(root.left);
        res += Serialize(root.right);
        return res;
    }

    /**
     * 将序列化字符串装入一个queue中
     */
    TreeNode Deserialize(String str) {
        Queue<String> queue = new LinkedList<>();
        Collections.addAll(queue, str.split("_"));
        return Deserialize(queue);
    }

    /**
     * 前序遍历反序列化
     * 从队列中取出一个判断是否是"#",如果是表示该结点为null,否则新建结点
     */
    private TreeNode Deserialize(Queue<String> queue) {
        String string = queue.poll();
        if (string.equals("#")) {
            return null;
        }
        TreeNode root = new TreeNode(Integer.parseInt(string));
        root.left = Deserialize(queue);
        root.right = Deserialize(queue);
        return root;
    }
}
发表于 2019-07-11 22:16:06 回复(2)
/*
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 回复(2)
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)

问题信息

难度:
446条回答 90382浏览

热门推荐

通过挑战的用户

查看代码