算法（4）二叉树的序列化和反序列化

1、二叉树序列化
1、 每个节点的值结束后加入 “！” 用来分割，当节点是 null 的时候插入 “#” 返回。

   //node 节点结构
   static class TreeNode {
       int val = 0;
       TreeNode left = null;
       TreeNode right = null;

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

   /**
     * 序列化，先序遍历
     * @param root
     * @param result
     */
   static void serializable(TreeNode root, StringBuilder result) {
        if (root != null) {
            result.append(root.val).append("!");
            serializable(root.left, result);
            serializable(root.right, result);
        } else {
            result.append("#!");
        }
    }

2、反序列化
1、根据“！” 将字符串分割成string数组
2、递归调用重建二叉树，先根据str[index] 是不是 “#”，判断是否需要新建一个节点，如果不是null，new一个新节点，然后递归调用重建它的左子树，之后是右子树。
3、需要维护一个全局变量来表示string数组当前的偏移位置。

    //
    static int index = 0;
    static TreeNode deserialize(String[] tree) {
        if ("#".equals(tree[index])) {
            index++;
            return null;
        } else {
            TreeNode node = new TreeNode(Integer.parseInt(tree[index++]));
            node.left = deserialize(tree);
            node.right = deserialize(tree);
            return node;
        }
    }

    static void solution(String str) {
        String[] strs = str.split("!");
        TreeNode node = deserialize(strs);
    }

public static void main(String[] args) {
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);
        TreeNode node8 = new TreeNode(8);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node3.left = node5;
        node3.right = node6;
        node5.left = node7;
        node5.right = node8;
        StringBuilder str = new StringBuilder("");
        serializable(node1, str);
        System.out.println(str);
        solution(str.toString());
    }