序列化二叉树

java递归，反序列化没有用String.spilt建立String数组，降低空间消耗。阶梯思路和大多数人的差不错，中序遍历。时间：32 ms 空间：9868K

String Serialize(TreeNode root) {
    if (root == null) return "#!";
    StringBuilder res = new StringBuilder();
    Serialize(root, res);
    return res.toString();
}

void Serialize(TreeNode root, StringBuilder res) {
    if (root == null) {
        res.append("#!");
        return;
    }
    res.append(root.val);
    res.append("!");
    Serialize(root.left, res);
    Serialize(root.right, res);
}

int index = 0;

TreeNode Deserialize(String str) {
    if (str == null) return null;
    int len = str.length();
    if (len == 0) return null;
    return construc(str);
}

TreeNode construc(String str) {
    if (index >= str.length()) return null;
    int i = index;
    while (str.charAt(index) != '!') {
        index++;
    }
    String root = str.substring(i, index++);
    TreeNode res = null;
    if (!"#".equals(root)) {
        res = new TreeNode(Integer.valueOf(root));
    } else {
        return null;
    }
    res.left = construc(str);
    res.right = construc(str);
    return res;
}