今日题目（剑指Offer系列）
剑指 Offer 37. 序列化二叉树
请实现两个函数，分别用来序列化和反序列化二叉树。
示例：
你可以将以下二叉树： 1 / \ 2 3 / \ 4 5 序列化为 "[1,2,3,null,null,4,5]"
解题思路：
>最开始我没看明白题是什么意思 >看了一下K神的题解，发现序列化好像就是按照层序遍历的方式遍历整棵树 >把null也确定进去 >反序列化就是将序列化好的字符串，还原成一颗二叉树
Python解法：
class Codec: def serialize(self, root): if not root: return "[]" queue = collections.deque() queue.append(root) res = [] while queue: node = queue.popleft() if node: res.append(str(node.val)) queue.append(node.left) queue.append(node.right) else: res.append("null") return '[' + ','.join(res) + ']' def deserialize(self, data): if data == "[]": return vals, i = data[1:-1].split(','), 1 root = TreeNode(int(vals[0])) queue = collections.deque() queue.append(root) while queue: node = queue.popleft() if vals[i] != "null": node.left = TreeNode(int(vals[i])) queue.append(node.left) i += 1 if vals[i] != "null": node.right = TreeNode(int(vals[i])) queue.append(node.right) i += 1 return root
Java解法：
public class Codec { // Encodes a tree to a single string. public String serialize(TreeNode root) { if(root == null) return "[]"; StringBuilder res = new StringBuilder("["); Queue<TreeNode> queue = new LinkedList<>() {{ 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(); } // Decodes your encoded data to tree. 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<>() {{ 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; } }
