[leetcode]449. Serialize and Deserialize BST设计BST的编解码

/*
    一开始想着中序遍历，但是解码的时候才发现，中序遍历并不能唯一得确定二叉树。
    后来看了网上的答案，发现先序遍历是可以的，观察了一下，对于BST，先序遍历确实是可以
    唯一得确定。
    对于一般的二叉树，必须是前序和中序或者后序和中序才能唯一确定，其中中序的作用就是
    确定中心位置，以确定左右子树的前序（后序）的范围
    但是对于BST根据性质，左子树的前序序列最大的就是1st节点，所以找到序列中第一个比
    1st节点大的节点就是右子树的开始，这样就不需要中序了
    还有一种方法，保存二叉树的结构信息，这种做法可以应用于任何二叉树。保存结构信息就是空节点添加一个符号代替，解码的时候就知道结构信息了
     */
    //记录数据
    StringBuilder s = new StringBuilder();
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        preTra(root);
        return new String(s);
    }
    //前序遍历
    public void preTra(TreeNode root)
    {
        if (root==null) return;
        s.append(root.val);
        s.append(",");
        preTra(root.left);
        preTra(root.right);
    }
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data.length()==0) return null;
        String[] vals = data.split(",");
        return helper(vals,0,vals.length-1);
    }
    //解码过程，和由前序及中序得到二叉树的过程类似
    public TreeNode helper(String[] data,int sta,int end)
    {
        if (sta > end) return null;
        //根据BST的特点，获得左右子树前序遍历序列的起止点
        int rightSta = rSta(data,sta,end);
        TreeNode cur = new TreeNode(Integer.parseInt(data[sta]));
        cur.left = helper(data,sta+1,rightSta-1);
        cur.right = helper(data,rightSta,end);
        return cur;
    }
    public int rSta(String[] data,int sta,int end)
    {
        /*
        第一个比根节点大的值就是右子树的开始
         */
        int a  = Integer.parseInt(data[sta]);
        while (sta<=end)
        {
            if (Integer.parseInt(data[sta])>a)
                break;
            sta++;
        }
        return sta;
    }

/*
    * 如果知道（中序遍历和前序遍历）或者（中序遍历和后序遍历）可以唯一确定一棵树*/
    /*
    由前序遍历和中序遍历确定二叉树
     */
    public TreeNode PaI(int[] pre,int[] in)
    {
        if (pre.length==0) return null;
        //只剩下一个节点，就直接返回这个节点
        if (pre.length==1)
            return new TreeNode(pre[0]);
        //根据前序遍历的开头获得中序遍历的中心
        int center = pre[0];
        int c = 0;
        for (int i = 0; i < in.length; i++) {
            if (in[i]==center)
            {
                c = i;
                break;
            }
        }
        //根据中序遍历和中心位置确定左右子树的前中序遍历序列，递归求子树
        //左右子树的中序遍历就是中心位置的左右子序列
        //左右子树的前序遍历序列是根节点后边序列分为的两部分，长度分别与其中序遍历序列长度一样
        TreeNode cur = new TreeNode(center);
        cur.left = PaI(Arrays.copyOfRange(pre,1, 1 + c),Arrays.copyOfRange(in,0,c));
        cur.right = PaI(Arrays.copyOfRange(pre,c+1,pre.length),Arrays.copyOfRange(in,c+1,in.length));
        return cur;
    }