一、题目信息
二、题目解读
我们需要制定出一套规则来完成二叉树的序列化与反序列化,
序列化规则将二叉树的结点按某种顺序转化为字符串
,反序列化规则将字符串恢复为二叉树
。这套规则对应的变换必须是双射的(一一对应的),即一棵二叉树只能与唯一一个字符串对应。
- 用字符#代表一个空结点(也是重要的一点)。
三、简单的分析
1.序列化
第二部分的第3点保证了空结点的可知,这样所有的结点都是可表示的。现在只要选取任何一种遍历方式就可以将一棵二叉树唯一地表示为一个字符串。
2.反序列化
考虑一下为什么根据前中序或者后中序可以恢复二叉树?
因为我们总可以根据前序或者后序找到根节点,然后在中序中确定根节点的左右子树,接着继续递归着构造下去。每个结点的父节点和孩子结点都是可确定的!
接下来就是找到可以轻松确定结点位置的规则,在序列化部分中我们可以使用4种遍历方式(前序、中序、后序和层次遍历),明显的层次遍历是我们的首选方式,原因(结合#的引入)是:
四、解题代码
1.C++
1 | /** |
2.Python
1 | # Definition for a binary tree node. |
- 其他题目、其他语言的解题代码请移步我的GitHub存储库。