剑指offer第二版-37.序列化二叉树

本系列导航：剑指offer（第二版）java实现导航帖

面试题37：序列化二叉树

题目要求：
实现两个函数，分别用来序列化和反序列化二叉树。

解题思路：
此题能让人想到重建二叉树。但二叉树序列化为前序遍历序列和中序遍历序列，然后反序列化为二叉树的思路在本题有两个关键缺点：1.全部数据都读取完才能进行反序列化。2.该方法需要保证树中节点的值各不相同（本题无法保证）。
其实，在遍历结果中，记录null指针后（比如用一个特殊字符$），那么任何一种遍历方式都能回推出原二叉树。但是如果期望边读取序列化数据，边反序列化二叉树，那么仅可以使用前序或层序遍历。但层序记录的null个数要远多于前序，因此选择使用记录null指针的前序遍历进行序列化。

package chapter4;
import structure.TreeNode;

/**
 * Created by ryder on 2017/7/19.
 * 序列化二叉树
 */
public class P194_SerializeBinaryTrees {
    public static String serialize(TreeNode<Integer> root){
        if(root==null)
            return "$,";
        StringBuilder result = new StringBuilder();
        result.append(root.val);
        result.append(",");
        result.append(serialize(root.left));
        result.append(serialize(root.right));
        return result.toString();
    }
    public static TreeNode<Integer> deserialize(String str){
        StringBuilder stringBuilder = new StringBuilder(str);
        return deserializeCore(stringBuilder);
    }
    public static TreeNode<Integer> deserializeCore(StringBuilder stringBuilder){
        if(stringBuilder.length()==0)
            return null;
        String num = stringBuilder.substring(0,stringBuilder.indexOf(","));
        stringBuilder.delete(0,stringBuilder.indexOf(","));
        stringBuilder.deleteCharAt(0);
        if(num.equals("$"))
            return null;
        TreeNode<Integer> node = new TreeNode<>(Integer.parseInt(num));
        node.left = deserializeCore(stringBuilder);
        node.right = deserializeCore(stringBuilder);
        return node;
    }
    public static void main(String[] args){
        //            1
        //          /   \
        //         2     3
        //       /      / \
        //      4      5   6
        //    1,2,4,$,$,$,3,5,$,$,6,$,$
        TreeNode<Integer> root = new TreeNode<Integer>(1);
        root.left = new TreeNode<Integer>(2);
        root.right = new TreeNode<Integer>(3);
        root.left.left = new TreeNode<Integer>(4);
        root.right.left = new TreeNode<Integer>(5);
        root.right.right = new TreeNode<Integer>(6);
        System.out.println("原始树："+root);
        String result = serialize(root);
        System.out.println("序列化结果："+result);
        TreeNode<Integer> deserializeRoot = deserialize(result);
        System.out.println("反序列后的树："+deserializeRoot);
    }
}

运行结果

原始树：[1,2,3,4,5,6]
序列化结果：1,2,4,$,$,$,3,5,$,$,6,$,$,
反序列后的树：[1,2,3,4,5,6]