序列化二叉树

采用的是层序遍历的方式：

import java.util.*;

public class Solution {
    // 序列化
    String Serialize(TreeNode root) {
        if (root == null) {
            return "";
        }
        StringBuilder sb = new StringBuilder();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            root = queue.poll();
            if (root == null) {
                sb.append("#!");
            } else {
                sb.append(root.val).append("!");
                queue.offer(root.left);
                queue.offer(root.right);
            }
        }
        return sb.toString();
    }

    // 反序列化
    TreeNode Deserialize(String str) {
        if (str == null || str.length() == 0)
           return null;
        String[] a = str.split("!");
        int len = a.length;
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode root = new TreeNode(Integer.valueOf(a[0]));
        queue.offer(root);
        int i = 1;
        while (!queue.isEmpty() && i < a.length) {
            TreeNode cur = queue.poll();
            if ("#".equals(a[i])) {
                cur.left = null;
            } else {
                cur.left = new TreeNode(Integer.valueOf(a[i]));
                queue.offer(cur.left);
            }
            ++i;
            if ("#".equals(a[i])) {
                cur.right = null;
            } else {
                cur.right = new TreeNode(Integer.valueOf(a[i]));
                queue.offer(cur.right);
            }
            ++i;
        }
        return root;
  }
}

知识点：

1. LinkedList中元素可以为null。
2. Integer的静态方法中，valueOf(String)返回的是Integer，而parseInt(String)返回的是int，尽量选择无需额外拆装箱的静态方法。
3. StringBuilder的包是java.lang，单纯使用它不用额外import。
4. String的split方法：

s.split("!")为例：

"" -> [""]
"1" -> ["1"]

"1!2" -> ["1", "2"]
"1!2!" -> ["1", "2"]
"1!2!!!!" -> ["1", "2"]

"!1!2!" -> ["", "1", "2"]
"!!!1!2!" -> ["", "", "", "1", "2"]

"1!!2" -> ["1", "", "2"]
"1!!!2" -> ["1", "", "", "2"]

可见，

• 不含分隔符的源字符串处理完成后，是长度为1的字符串数组，元素就是源字符串。
• 结尾的多余的分隔符不影响结果。
• 开头和中间的多余的分隔符会影响结果。