题目
序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。
请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
提示: 输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。
示例 1：
输入：root = [1,2,3,null,null,4,5] 输出：[1,2,3,null,null,4,5]
示例 2：
输入：root = [] 输出：[]
示例 3：
输入：root = [1] 输出：[1]
示例 4：
输入：root = [1,2] 输出：[1,2]
解题
方法一：层序遍历
如：二叉树[1,2,3,null,null,4,null]序列化后的结果为[1,2,3,null,null,4,null,null,null]，这样子反序列化过程中，索引i就不会超过范围
下面用"#"代表null部分
# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Codec: def serialize(self, root): """Encodes a tree to a single string. :type root: TreeNode :rtype: str """ if not root: return "" res = [] queue = [root] while queue: cur =queue.pop(0) if cur: queue.append(cur.left) queue.append(cur.right) res.append(str(cur.val)) else: res.append("#") return ",".join(res) def deserialize(self, data): """Decodes your encoded data to tree. :type data: str :rtype: TreeNode """ if data == "": return None rec = data.split(',') root = TreeNode(rec[0]) queue = [root] i = 1 while queue: p = queue.pop(0) if rec[i] != "#": p.left = TreeNode(int(rec[i])) queue.append(p.left) i += 1 if rec[i] != "#": p.right = TreeNode(int(rec[i])) queue.append(p.right) i += 1 return root # Your Codec object will be instantiated and called as such: # ser = Codec() # deser = Codec() # ans = deser.deserialize(ser.serialize(root))
注意要先p.left = TreeNode(int(rec[i]))后queue.append(p.left)，创建好节点，才能加入队列
c++ 写法
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Codec { public: string join(vector<string>& vec){ int n=vec.size(); string res; for(int i=0;i<n;i++){ res+=vec[i]; if(i!=n-1) res+=","; } return res; } vector<string> split(string& s){ vector<string> res; int i=0,n=s.size(); while(i<n){ int start=i; while(i<n&&s[i]!=',') i++; res.push_back(s.substr(start,i-start)); i++;//跳过逗号 } return res; } // Encodes a tree to a single string. string serialize(TreeNode* root) { if(root==nullptr) return ""; queue<TreeNode*> q; q.push(root); vector<string> vec; while(!q.empty()){ TreeNode* cur=q.front(); q.pop(); if(cur){ q.push(cur->left); q.push(cur->right); vec.push_back(to_string(cur->val)); }else{ vec.push_back("#"); } } string res=join(vec); return res; } // Decodes your encoded data to tree. TreeNode* deserialize(string data) { if(data.size()==0) return nullptr; vector<string> vec=split(data); TreeNode* root=new TreeNode(stoi(vec[0])); queue<TreeNode*> q; q.push(root); int i=1; while(!q.empty()){ TreeNode* cur=q.front(); q.pop(); if(vec[i]!="#"){ cur->left=new TreeNode(stoi(vec[i])); q.push(cur->left); } i++; if(vec[i]!="#"){ cur->right=new TreeNode(stoi(vec[i])); q.push(cur->right); } i++; } return root; } }; // Your Codec object will be instantiated and called as such: // Codec ser, deser; // TreeNode* ans = deser.deserialize(ser.serialize(root));
方法二：先序遍历：使用递归
# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Codec: def serialize(self, root): """Encodes a tree to a single string. :type root: TreeNode :rtype: str """ def dfs(node): if node: vals.append(str(node.val)) dfs(node.left) dfs(node.right) else: vals.append("#") vals = [] dfs(root) return ",".join(vals) def deserialize(self, data): """Decodes your encoded data to tree. :type data: str :rtype: TreeNode """ def dfs(): v = next(vals) if v == "#": return None node = TreeNode(int(v)) node.left = dfs() node.right = dfs() return node vals = iter(data.split(",")) return dfs() # Your Codec object will be instantiated and called as such: # ser = Codec() # deser = Codec() # ans = deser.deserialize(ser.serialize(root))
