297. Serialize and Deserialize Binary Tree二叉树的序列化和反序列化（就用Q）

［抄题］：

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   5

as "[1,2,3,null,null,4,5]"

 [暴力解法]：

时间分析：

空间分析：

 [优化后]：

时间分析：

空间分析：

［奇葩输出条件］：

［奇葩corner case］：

［思维问题］：

不知道空节点怎么处理：随便用一个什么字符串代替就行了，反正压缩之后也看不见

［英文数据结构或算法，为什么不用别的数据结构或算法］：

pre-order，写着方便

用deque，先都存了，然后全部先进先出

［一句话思路］：

把空节点提前定义为一个特殊的字符串来处理

［输入量］：空： 正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：

需要提前定义 spliter = ","

［画图］：

［一刷］：

1. 节点为空和新建树是两个独立的过程，需要用if else隔开
2. 反序列化只需要用q做参数即可，因为节点都是recursion中新建的

［二刷］：

1. 节点为空就是root本身 == null, 不是root.val == null
2. 写公式就完成recursion了，此时可以return

［三刷］：

1. 字符串判断相等应该用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<String> queue = new LinkedList<>();
        
        //put into queue
        queue.addAll(Arrays.asList(data.split(",")));
        
        return buildTree(queue);
    }
    
    private TreeNode buildTree(Deque<String> 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));