Binary tree serialization and deserialization

---

二叉树的序列化:二叉树被记录成文件的过程(持久化过程) 反序列化:通过文件内容重建原来的二叉树的过程叫做二叉树的反序列化.(deserializable)

序列化的方式:

1. 根据先序遍历序列化
2. 根据中序遍历序列化
3. 根据后续遍历序列化
4. 按层序列化 给定一棵二叉树的头结点head,并已知二叉树节点值的类型为32位整型. 请设计一种二叉树序列化和反序列化的方案,并用代码实现.

先序遍历对二叉树进行序列化

1. 假设序列化结果为str,初始时str为空字符串.
2. 先序遍历二叉树时如果遇到空节点,在str末尾加上"#!"
3. 如果遇到不为null的节点,假设节点值为3,就在str的末尾加上"3!".

二叉树的初始样式<br>
           12
          /  \
         3    null
        /  \   
      null null

序列化结果为12!3!#!#!#!

用#!来替代null(念shap) 如果不用特殊符号!表示值的结束,则这两棵树的序列换结果为: 123###,说明不用特殊符号表示节点值结束的话,会产生歧义. 反序列化的时候,就有可能不是同一棵树,比如可能是下面这种形式

       1
     /  \
    2    3
   / \   
null null

一棵二叉树通过先序遍历得到的结果,如何进行反序列化?

str="12!3!#!#!#!" values=["12"."3"."#"."#"."#"]

结果如下:<br>
             12
           /   \
          3     null
         / \
     null  null

• 总结:
• 1.选择什么样的遍历方式序列化,就选择用什么样的方式反序列化
• 2.一棵树序列化的结果是唯一的,唯一的结果生成的二叉树也是唯一的.