题目描述

请实现两个函数，分别用来序列化和反序列化二叉树

二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#），以 ！ 表示一个结点值的结束（value!）。

二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。

题解一

这题的细节特别麻烦，折腾了好久才AC成功。本题对于二叉树的序列化和反序列化的规则是自定义的，即给定一个二叉树，可以以自定义的规则进行序列化，但是要保证反序列化出的二叉树和输入的二叉树一模一样。我的规则是在每个节点后输出一个逗号，例如：

    1
   / \
  2   3
     / \
    4   5

输入的二叉树如上所示，经序列化后，得到字符串："1,2,#,#,3,4,#,#,5,#,#,"

这里使用先序遍历的深度优先查找，序列化二叉树即在先序遍历二叉树时将节点输出。重点是在碰到空节点时也要输出#，因为序列中的#能够决定二叉树的结构，没有这个空节点#，单靠先序序列是无法恢复出原来的二叉树的，即反序列化。

在反序列化时，也是使用先序遍历的模板，用到了StringBuilder这个数据结构，而不直接用String。因为String在java中是不可变对象，是被final修饰的，每次对String修改，都会创建一个新的String，浪费时间和空间。除了StringBuilder，也可以考虑使用字符数组的方式，这就需要考虑索引的问题了。

下面是参考代码：

public String serialize(TreeNode root) {
    StringBuilder builder = new StringBuilder();
    serializeHelper(root, builder);
    return builder.toString();
}

private void serializeHelper(TreeNode node, StringBuilder builder) {
    if (node == null) {
        builder.append("#,");
        return;
    }
    builder.append(node.val).append(',');
    serializeHelper(node.left, builder);
    serializeHelper(node.right, builder);
}

public TreeNode deserialize(String str) {
    return deserializeHelper(new StringBuilder(str));
}

private TreeNode deserializeHelper(StringBuilder builder) {
    // 递归终止条件与空节点的处理
    if (builder.length() == 0)
        return null;
    if (builder.charAt(0) == '#') {
        builder.delete(0,2);
        return null;
    }

    // 取出当前根节点的值存进num
    int index = builder.indexOf(",");
    int num = Integer.parseInt(builder.substring(0,index));
    builder.delete(0,index+1);

    // 先序遍历
    TreeNode root = new TreeNode(num);
    root.left = deserializeHelper(builder);
    root.right = deserializeHelper(builder);
    return root;
}