2018-01-23 二叉树的序列化反序列化

设计一个算法，并编写代码来序列化和反序列化二叉树。将树写入一个文件被称为“序列化”，读取文件后重建同样的二叉树被称为“反序列化”。

如何反序列化或序列化二叉树是没有限制的，你只需要确保可以将二叉树序列化为一个字符串，并且可以将字符串反序列化为原来的树结构。

public class Demo2 {
    /**
     *     1
     *   2     3
     * 4  5  6
     * @param args
     */
    public static void main(String[] args) {
        TreeNode A = new TreeNode(1);
        TreeNode B = new TreeNode(2);
        TreeNode C = new TreeNode(3);
        TreeNode D = new TreeNode(4);
        TreeNode E = new TreeNode(5);
        TreeNode F = new TreeNode(6);

        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;

      String s = Serialize(A);
      System.out.println(s);
      Deserialize(s);
    }

    static StringBuilder sb = null;

    static String Serialize(TreeNode root) {
        if (root == null)
            return "#";
        sb = new StringBuilder();
        Serialize_solve(root);
        String s = sb.toString();
        return s.substring(0, s.length() - 1); //这里减1是因为最后有一个',' 截取掉他
//        return s;
    }

    private static void Serialize_solve(TreeNode root) {
        if (root == null) {
            sb.append("#,");
            return;
        }
        sb.append(root.val + ",");
        Serialize_solve(root.left);
        Serialize_solve(root.right);
    }

    static int index;

    static TreeNode Deserialize(String str) {
        if (str == null || str.trim().equals(""))
            return null;

        String[] strs = str.split(","); 
        index = 0;
        return Deserialize_solve(strs);
    }

    private static TreeNode Deserialize_solve(String[] chars) {
        if (chars[index].equals("#")) {
            index++;
            return null;
        }
        System.out.println(chars[index]);
        TreeNode node = new TreeNode(Integer.parseInt(chars[index++]));
        node.left = Deserialize_solve(chars);
        node.right = Deserialize_solve(chars);

        return node;
    }

}

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

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

    }
}

输出:

1,2,4,#,#,5,#,#,3,6,#,#,#
1
2
4
5
3
6