/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {
    //对于这个问题我们首先得想要序列化一个二叉树，首先得遍历一遍二叉树才行，遍历的选择有四种分别为层次遍历，前序，中序后序遍历
    //如果选用层次遍历很难分辨哪一层是哪几个节点所以果断不选用
    //对于中序遍历来说在反序列化时首先重建的是最左下角的子树，循环重建右上角的子树，这存在一个问题就是重建的子树的的父节点还不存存在很难给其赋值
    //对于后序遍历来说毛病和中序一样
    //所以我们选用前序遍历来解决这问题，前序遍历再反序列化时先创建根节点再考虑创建其左右子树，这样来说左右子树相对好赋值一些，并且从上到下具备一定的递归性质
    //需要注意的是树中的空节点我们需要使用“#”来代替不然多种不同的树序列化后结果相同，但是反序列化只能序列化出其中一颗树，达不到我们的目的。
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        //序列化采用前序遍历的方式，首先序列化本节点，然后将其左右子树序列化
        //首先得考虑好递归条件，当节点为空时序列化的节点为空时使用#来替代
        if(root == null){
            return "#";
        }
        //接着记录下来本节点的序列结果
        //序列化左子树,并且记录下来结果
        String left = serialize(root.left);
        //序列化右子树并且记录下来结果
        String right = serialize(root.right);
        return String.valueOf(root.val) + "," + left + "," + right;
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        //递归参数准备阶段
        //首先处理序列化字符串为字符串数组，后续需要逐个遍历字符串数组来的得到结果
        String[] strs = data.split(",");
        //创建一个一位的数组来记录遍历的下标，由于我们使用的时递归而且遍历完成一个字符串之后下标必须移动，接着遍历下一个下标，又由于java的值传递的性质所以我们只能通过一个数组来的使得在下一次遍历的时候得到最新遍历的下标值
        int[] index = {0};
        //递归遍历
        return getTree(strs,index);
    }

    //这个递归函数其实定义的就是我们在遍历每一个字符串时需要做什么，千万不要去逐个分析递归（会疯的），我们在使用和分析递归时最好去分析每次递归做了什么然后再具体分析整个递归下来结果是什么，并且合理设置递归出口。
    public TreeNode getTree(String[] tree,int[] index){
        //由于整个序列化的过程采用的时前序遍历所以我们再反序列化的时候也需要使用前序遍历的规则来反序列化回去
        //首先取出当前位置的值，并改变下标
        String value = tree[index[0]];
        index[0]++;
        //根据取出的值来判断是不是空节点，再选择要不要创建节点
        if(value.equals("#")){
            return null;
        }
        TreeNode node = new TreeNode(Integer.valueOf(value));
        //创建左子树
        node.left = getTree(tree,index);
        //创建右子树
        node.right = getTree(tree,index);
        //返回结果
        return node;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));