［抄题］：
Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.
Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.
Example:
You may serialize the following tree: 1 / \ 2 3 / \ 4 5as "[1,2,3,null,null,4,5]"
[暴力解法]：
时间分析：
空间分析：
[优化后]：
时间分析：
空间分析：
［奇葩输出条件］：
［奇葩corner case］：
［思维问题］：
不知道空节点怎么处理：随便用一个什么字符串代替就行了，反正压缩之后也看不见
［英文数据结构或算法，为什么不用别的数据结构或算法］：
pre-order，写着方便
用deque，先都存了，然后全部先进先出
［一句话思路］：
把空节点提前定义为一个特殊的字符串来处理
［输入量］：空： 正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：
需要提前定义 spliter = ","
［画图］：
［一刷］：
- 节点为空和新建树是两个独立的过程，需要用if else隔开
- 反序列化只需要用q做参数即可，因为节点都是recursion中新建的
［二刷］：
- 节点为空就是root本身 == null, 不是root.val == null
- 写公式就完成recursion了，此时可以return
［三刷］：
- 字符串判断相等应该用equals
［四刷］：
［五刷］：
[五分钟肉眼debug的结果]：
［总结］：
光有死记硬背不行，一点不背想凭空写 更是无稽之谈
［复杂度］：Time complexity: O(n) Space complexity: O(n)
［算法思想：递归/分治/贪心］：递归
［关键模板化代码］：
［其他解法］：
［Follow Up］：
［LC给出的题目变变变］：
271. Encode and Decode Strings就是用stringbuilder就行了
449. Serialize and Deserialize BST 不能中序，因为对递增有要求，输入串未必满足
[代码风格] ：
[是否头一次写此类driver funcion的代码] ：
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */public class Codec { //ini: split, null private static final String split = ","; private static final String NN = " "; // Encodes a tree to a single string. public String serialize(TreeNode root) { //new StringBuilder StringBuilder sb = new StringBuilder(); // buildString(root, sb); return sb.toString(); } private void buildString(TreeNode root, StringBuilder sb) { //if null, else preorder if (root == null) { sb.append(NN).append(split); }else { sb.append(root.val).append(split); buildString(root.left, sb); buildString(root.right, sb); } } // Decodes your encoded data to tree. public TreeNode deserialize(String data) { //ini: deque Deque queue = new LinkedList<>(); //put into queue queue.addAll(Arrays.asList(data.split(","))); return buildTree(queue); } private TreeNode buildTree(Deque queue) { String val = queue.remove(); //if null if (val.equals(NN)) { return null; }else { //else: preoder, return TreeNode node = new TreeNode(Integer.valueOf(val)); node.left = buildTree(queue); node.right = buildTree(queue); return node; } }}// Your Codec object will be instantiated and called as such:// Codec codec = new Codec();// codec.deserialize(codec.serialize(root));