题目:序列化二叉树
请实现两个函数,分别用来序列化和反序列化二叉树。
将树写入一个文件被称为“序列化”,读取文件后重建同样的二叉树被称为“反序列化”。
二叉树节点
1 | private static class BinaryTreeNode { |
举例说明
二叉树
1 | 1 |
按前序遍历(只有前序遍历从根节点开始)系列化之后:
1 | 1,2,4,$,$,$,3,5,$,$,6,$,$, |
思路
- 以前的先序和后序遍历序列重构二叉树存在缺点:
- 要求二叉树中没有数值相同的结点
- 要求整个序列都读出后才能开始重构,如果序列是流式输入,那么就需要等待序列输出完毕才能完成二叉树的重构
- 利用先序遍历
- node之间用
,
隔开 - 保存二叉树空结点为
$
利用这样的序列,就可以规避上面存在的两种缺点。
代码实现
1 | import java.util.LinkedList; |