剑指offer037序列化和反序列化二叉树

Problem:

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

Solution:

public class CodingInterview_037 {
    public static void main(String[] args) {
        //这一题我们需要先明确serialze之后表示树的字符串长成什么样子，比如一个最简单的树以1为root，2，3分别为其左右节点的树经过前序遍历的字符串打印出来应该是：1,2,#,#,3,#,#,的
        TreeNode t=new TreeNode(1);
        t.left=new TreeNode(2);
        t.right=new TreeNode(3);
        CodingInterview_037 c=new CodingInterview_037();
        String s=c.Serialize(t);
        System.out.println(s);
    }


    int index=-1;
    public String Serialize(TreeNode root) {
        //通过前序遍历构建二叉树字符串
        StringBuilder sb = new StringBuilder();
        if(root == null){
            sb.append("#,");
            return sb.toString();
        }
        sb.append(root.val + ",");
        sb.append(Serialize(root.left));
        sb.append(Serialize(root.right));
        return sb.toString();
    }
    public TreeNode Deserialize(String str) {
        String[] numberArray=str.split(",");
        TreeNode node=DeserialzieArray(numberArray);
        return node;
    }
    //下面这种解法是错误范例，结合例子很容易就看出来右子树的下标不对，这种情况下我们应该用全局变量来处理，让递归函数自己递增下标。
    /*
    private TreeNode DeserialzieArray(String[] numberArray,int index){
        if(numberArray[index].equals("#")){
            return null;
        }else{
            TreeNode node=new TreeNode(Integer.parseInt(numberArray[index]));
            node.left=DeserialzieArray(numberArray,index+1);
            node.right=DeserialzieArray(numberArray,index+2);
            return node;
        }
    }
    */
    //像这种感觉需要返回多个值的递归问题，我们都可以采用全局变量来处理。本题中用全局变量index来追踪index的位置
    private TreeNode DeserialzieArray(String[] numberArray){
        index++;
        if(numberArray[index].equals("#")){
            return null;
        }else{
            TreeNode node=new TreeNode(Integer.parseInt(numberArray[index]));
            node.left=DeserialzieArray(numberArray);
            node.right=DeserialzieArray(numberArray);
            return node;
        }
    }



}