序列化二叉树

题目：

​ 请实现两个函数，分别用来序列化和反序列化二叉树。

分析：

1. 根据 “重建二叉树” ，我们知道可以从前序遍历序列和中序遍历序列 中构造出一棵二叉树。受此启发，我们可以把一棵二叉树序列化成一个前序遍历序列和一个中序遍历序列，然后在反序列化时通过这两个序列构造出一棵二叉树。
2. 这种思路有两个缺点：
   • 该方法要求二叉树不能有重复的节点；
   • 只有当两个序列中所有数据都读出后才能开始反序列化。
3. 实际上，如果二叉树的序列化是从根节点开始的，那么反序列化在根节点的数据读取出来后就可以开始了。因此这里根据前序遍历的顺序来序列化二叉树，因为前序遍历是从根节点开始的。
4. 在遍历二叉树时碰到空节点，使用特殊字符表示（如 “$”），节点数值之间用 “,” 分隔。

代码：

public class SerializeBinaryTree {
    private static int index = -1;

    public static String serialize(BinaryTreeNode pRoot) {
        StringBuilder sb = new StringBuilder();
        if (null == pRoot) {
            sb.append("$").append(",");
            return sb.toString();
        }

        sb.append(pRoot.value).append(",");
        sb.append(serialize(pRoot.left));
        sb.append(serialize(pRoot.right));
        return sb.toString();
    }

    public static BinaryTreeNode deSerialize(String str) {

        String[] splitArr = str.split(",");
        index++;
        BinaryTreeNode pNode = null;
        if (!"$".equals(splitArr[index])) {
            pNode = new BinaryTreeNode(Integer.parseInt(splitArr[index]));
            pNode.left = deSerialize(str);
            pNode.right = deSerialize(str);
        }
        return pNode;
    }
}

测试：

public class TestSerializeBinaryTree {

    BinaryTreeNode root1 = new BinaryTreeNode(10);

    @Before
    public void before() {

        BinaryTreeNode nodeA21 = new BinaryTreeNode(6);
        BinaryTreeNode nodeA22 = new BinaryTreeNode(14);
        BinaryTreeNode nodeA31 = new BinaryTreeNode(4);
        BinaryTreeNode nodeA32 = new BinaryTreeNode(8);
        BinaryTreeNode nodeA33 = new BinaryTreeNode(12);
        BinaryTreeNode nodeA34 = new BinaryTreeNode(16);

        buildTree(root1, nodeA21, nodeA22);
        buildTree(nodeA21, nodeA31, nodeA32);
        buildTree(nodeA22, nodeA33, nodeA34);
    }

    private void buildTree(BinaryTreeNode root, BinaryTreeNode left, BinaryTreeNode right) {
        root.left = left;
        root.right =right;
    }

    @Test
    public void test() {
        System.out.println(SerializeBinaryTree.serialize(root1));
        BinaryTreeNode root = SerializeBinaryTree.deSerialize("10,6,4,$,$,8,$,$,14,12,$,$,16,$,$,");
        System.out.println(root.value);
    }
}