序列化(serialization)在计算机科学的数据处理中,是指将数据结构或对象状态转换成可取用格式(例如存成文件,存于缓冲,或经由网络中发送),以留待后续在相同或另一台计算机环境中,能恢复原先状态的过程。依照序列化格式重新获取字节的结果时,可以利用它来产生与原始对象相同语义的副本。对于许多对象,像是使用大量引用的复杂对象,这种序列化重建的过程并不容易。面向对象中的对象序列化,并不概括之前原始对象所关系的函数。这种过程也称为对象编组(marshalling)。从一系列字节提取数据结构的反向操作,是反序列化(也称为解编组、deserialization、unmarshalling)。
前序遍历
,中序遍历
, 后序遍历
。即如果先访问根节点就是前序遍历,最后访问根节点就是后续遍历,其它则是中序遍历。而左右节点的相对顺序是不会变的,一定是先左后右。当然也可以设定为先右后左。
105. 从前序与中序遍历序列构造二叉树
的解法,一行代码都不改。知道了三种遍历结果中的任意两种即可还原出原有的树结构
是不对的,严格来说应该是如果树中不存在重复的元素,那么知道了三种遍历结果中的任意两种即可还原出原有的树结构。i = inorder.index(root.val)
,如果存在重复元素,那么得到的索引 i 就可能不是准确的。但是,如果题目限定了没有重复元素则可以用这种算法。但是现实中不出现重复元素不太现实,因此需要考虑其他方法。那究竟是什么样的方法呢? 接下来进入正题。[1,2,3,null,null,4,5]
(本质上是 BFS 层次遍历),对应的树如下:选择这种记法,而不是 DFS 的记法的原因是看起来比较直观
[1,2,3,null,null,4,5]
会被处理为1,2,#,#,3,4,#,#,5,#,#
[1,2,#,#,3,4,#,#,5,#,#]
,然后我们同样执行一次前序遍历,每次处理一个元素,重建即可。由于我们采用的前序遍历,因此第一个是根元素,下一个是其左子节点,下下一个是其右子节点。即第 1 个节点的左右子节点对应第 1 个和第 2 个节点,第 2 个节点的左右子节点对应第 3 个和第 4 个节点。。。
(注意,没了下一层三个字)