面试题37：序列化和反序列化二叉树

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

序列化，递归函数传入一个节点，一个字符串，函数中分为两种，如果当亲节点为空，则转化为#，否则加入节点数字，然后依次对左右节点做同样操作。

反序列化，同样递归函数，将字符串去掉逗号转化为字符串数组。设置一个全局索引记录反序列化的位置，递归函数参数为字符串数组，首先给索引加1（初始为-1），如果当前字符是#号或者索引越界则返回空，否则构造新节点，左右子树调用自身形成，最后返回根节点。
代码如下

public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;

        }

    }

    /**
     * 使用递归
     * 1. 对于序列化：使用前序遍历，递归的将二叉树的值转化为字符，并且在每次二叉树的结点
     * 不为空时，在转化val所得的字符之后添加一个' ， '作为分割。对于空节点则以 '#' 代替。
     * 2. 对于反序列化：按照前序顺序，递归的使用字符串中的字符创建一个二叉树
     */
    //全局变量索引记录字符串位置
    private int index = -1;
    String Serialize(TreeNode root) {
        if (root == null) return "";
        StringBuilder sb = new StringBuilder();
        preOrder(root,sb);
        return sb.toString();
    }

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

    }

    TreeNode Deserialize(String str) {
        if (str.isEmpty()) return null;
        String[] seq = str.split(",");
        return reConstruct(seq);
    }

    private TreeNode reConstruct(String[] seq) {

        ++index;
        if (seq[index].equals("#") || index >= seq.length) return null;

        TreeNode root = new TreeNode(Integer.parseInt(seq[index]));
        root.left = reConstruct(seq);
        root.right = reConstruct(seq);

        return root;
    }