37-序列化二叉树

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

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

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

二叉树的遍历方式有前序 中序和后序遍历，前序遍历时是先处理根节点，然后分别处理左右子节点，这样在反序列化时我们就可以先生成根节点，然后递归的生成左右子树。对于Null节点 可以使用$代替。

private StringBuilder sb = new StringBuilder();
    String Serialize(TreeNode root) {
        if (root == null) {
            return sb.toString();
        }
        traverse(root);
        String result = sb.toString();
        result = result.substring(0, result.length() - 1);
        return sb.toString();
    }

    void traverse(TreeNode root) {
        //如果节点是null 使用$代替
        if (root == null) {
            sb.append("$,");
            return;
        }
        sb.append(root.val + ",");
        traverse(root.left);
        traverse(root.right);
    }

    TreeNode Deserialize(String str) {
        if (str == null || str.length() == 0) {
            return null;
        }
        String[] arr = str.split(",");
        TreeNode node = composite(arr);
        return node;
    }
    private int start = -1;
    TreeNode composite(String[] arr) {
        start++;
        if (start >= arr.length) {
            return null;
        }
        String val = arr[start];
        TreeNode root = null;
        if(val.equals("$")){
            return root;
        }
        //创建root节点 然后分别构建左右子树
        root = new TreeNode(Integer.parseInt(val));
        TreeNode left = composite(arr);
        TreeNode right = composite(arr);
        root.left = left;
        root.right = right;
        return root;
    }