AI summary
type
status
date
slug
summary
category
tags
icon
password

后序的妙用

复述下前文关于后序遍历的描述：
前序位置的代码只能从函数参数中获取父节点传递来的数据，而后序位置的代码不仅可以获取参数数据，还可以获取到子树通过函数返回值传递回来的数据。
那么换句话说，一旦你发现题目和子树有关，那大概率要给函数设置合理的定义和返回值，在后序位置写代码了。
多说无益，我们直接看题。

652. 寻找重复的子树

给你一棵二叉树的根节点 root ，返回所有 重复的子树 。
对于同一类的重复子树，你只需要返回其中任意 一棵 的根结点即可。
如果两棵树具有 相同的结构 和 相同的结点值 ，则认为二者是 重复 的。
我来简单解释下题目，输入是一棵二叉树的根节点 root，返回的是一个列表，里面装着若干个二叉树节点，这些节点对应的子树在原二叉树中是存在重复的。
这题咋做呢？还是老套路，先思考，对于某一个节点，它应该做什么。
如果你想知道以自己为根的子树是不是重复的，是否应该被加入结果列表中，你需要知道什么信息？
你需要知道以下两点：
  1. 以我为根的这棵二叉树（子树）长啥样？
  1. 以其他节点为根的子树都长啥样？
这就叫知己知彼嘛，我得知道自己长啥样，还得知道别人长啥样，然后才能知道有没有人跟我重复，对不对？好，那我们一个一个来看。
首先来思考，我如何才能知道以自己为根的这棵二叉树长啥样？
其实想到这里，就可以判断本题需要在二叉树的后序位置写代码了。
为什么？很简单呀，我要知道以自己为根的子树长啥样，是不是得先知道我的左右子树长啥样，再加上自己，就构成了整棵子树的样子？左右子树的样子，可不就得在后序位置通过递归函数的返回值传递回来吗？
现在，明确了要用后序遍历，那应该怎么描述一棵二叉树的模样呢？我们后文 序列化和反序列化二叉树 其实写过了，二叉树的前序/中序/后序/层序遍历结果可以描述二叉树的结构。
那么，我就以后序遍历结果作为序列化结果吧，可以通过拼接字符串的方式把二叉树序列化：
我们用非数字的特殊符 # 表示空指针，并且用字符 , 分隔每个二叉树节点值，这属于序列化二叉树的套路了，不多说。
注意我们 myself 是按照左子树、右子树、根节点这样的顺序拼接字符串，也就是后序遍历顺序。因为我们这里的目的是通过序列化唯一描述一棵二叉树的结构，所以你也可以用前序顺序来拼接字符串，但是注意不能用中序顺序，具体原因参见后文的总结。
现在我们解决第二个问题，我知道了自己长啥样，怎么知道别人长啥样？这样我才能知道有没有其他子树跟我重复对吧。
这很简单呀，我们借助一个外部数据结构，让每个节点把自己子树的序列化结果存进去，这样，对于每个节点，不就可以知道有没有其他节点的子树和自己重复了么？
初步思路可以使用 HashSet 记录所有子树的序列化结果，但是呢，这有个问题，如果出现多棵重复的子树，结果集 res 中必然出现重复，而题目要求不希望出现重复。
为了解决这个问题，可以把 HashSet 升级成 HashMap，额外记录每棵子树的出现次数，只有之前只出现过一次才加入 res 。
完整代码如下：

序列化与反序列化

前文 二叉树心法（构造篇） 带你学习了二叉树构造技巧，本文加大难度，让你对二叉树同时进行「序列化」和「反序列化」。
要说序列化和反序列化，得先从 JSON 数据格式说起。
JSON 的运用非常广泛，比如我们经常将编程语言中的结构体序列化成 JSON 字符串，存入缓存或者通过网络发送给远端服务，消费者接受 JSON 字符串然后进行反序列化，就可以得到原始数据了。
这就是序列化和反序列化的目的，以某种特定格式组织数据，使得数据可以独立于编程语言。
那么假设现在有一棵用 Java 实现的二叉树，我想把它通过某些方式存储下来，然后用 C++ 读取这棵并还原这棵二叉树的结构，怎么办？这就需要对二叉树进行序列化和反序列化了。

二叉树的唯一性

谈具体的题目之前，我们先思考一个问题：什么样的序列化的数据可以反序列化出唯一的一棵二叉树？
比如说，如果给你一棵二叉树的前序遍历结果，你是否能够根据这个结果还原出这棵二叉树呢？
答案是也许可以，也许不可以，具体要看你给的前序遍历结果是否包含空指针的信息。如果包含了空指针，那么就可以唯一确定一棵二叉树，否则就不行。
举个例子：
notion image
不包含空指针的前序遍历结果都为 [1,2,3,4,5] ，包含空指针的前序遍历结果分别为：[1,2,3,#,#,4,#,#,5,#,#] 和  [1,2,#,3,#,#,4,5,#,#,#]，它俩就区分开了。
但是，即便你包含了空指针的信息，也只有前序和后序的遍历结果才能唯一还原二叉树，中序遍历结果做不到。
因为前序/后序遍历的结果中，可以确定根节点的位置，而中序遍历的结果中，根节点的位置是无法确定的。反序列化必须先确定根节点的位置，先还原出根节点，再还原左右子树。
更直观的，比如如下两棵二叉树显然拥有不同的结构，但它俩的中序遍历结果都是 [#,1,#,1,#]，无法区分：
notion image
说了这么多，总结下结论，当二叉树中节点的值不存在重复时：
  1. 如果你的序列化结果中不包含空指针的信息，且你只给出一种遍历顺序，那么你无法还原出唯一的一棵二叉树。
  1. 如果你的序列化结果中不包含空指针的信息，且你会给出两种遍历顺序，那么分两种情况：
    1. 如果你给出的是前序和中序，或者后序和中序，那么你可以还原出唯一的一棵二叉树。
    2. 如果你给出前序和后序，那么你无法还原出唯一的一棵二叉树。
  1. 如果你的序列化结果中包含空指针的信息，且你只给出一种遍历顺序，也要分两种情况：
    1. 如果你给出的是前序或者后序，那么你可以还原出唯一的一棵二叉树。
    2. 如果你给出的是中序，那么你无法还原出唯一的一棵二叉树。

297. 二叉树的序列化与反序列化

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。
请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
提示: 输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。
想象一下，二叉树是一个二维平面内的结构，而序列化出来的字符串是一个线性的一维结构。所谓的序列化不过就是把结构化的数据「打平」，本质就是在考察二叉树的遍历方式。
二叉树的遍历方式有哪些？递归遍历方式有前序遍历，中序遍历，后序遍历；迭代方式一般是层级遍历。本文就把这些方式都尝试一遍，来实现 serialize 方法和 deserialize 方法。
前序遍历
就按照前序遍历即可，用 , 作为分隔符，用 # 表示空指针。
代码如下：
现在，思考一下如何写 deserialize 函数，将字符串反过来构造二叉树。
首先我们可以把字符串转化成列表，也就是二叉树的前序遍历结果，问题转化为：如何通过二叉树的前序遍历结果还原一棵二叉树？
根据树的递归性质，列表的第一个元素就是一棵树的根节点，所以只要将列表的第一个元素取出作为根节点，剩下的交给递归函数去解决即可。
代码如下：
注意：如果 nodes 用列表存储，那么 pop(0) 的操作很费时 。所以这里使用双端队列 deque
后序遍历
后序遍历的 serialize 序列化方法非常容易实现，简单改改即可。
关键点在于，如何实现后序遍历的 deserialize 方法呢？是不是也简单地将反序列化的关键代码无脑放到后序遍历的位置就行了呢？
显然不行。生搬硬套肯定是行不通的，回想刚才我们前序遍历方法中的 deserialize 方法，第一件事情在做什么？
deserialize 方法首先寻找 root 节点的值，然后递归计算左右子节点。那么我们这里也应该顺着这个基本思路走，后序遍历中，root 节点的值能不能找到？
当然可以，root 就是列表最后一个元素。所以我们应该从后往前取出列表元素，先用最后一个元素构造 root，然后递归调用生成 root 的左右子树。
notion image
注意，根据上图，从后往前在 nodes 列表中取元素，一定要先构造 root.right 子树，后构造 root.left 子树。
层级遍历
把标准的层级遍历框架稍作修改即可得到 serialize 函数：
层级遍历序列化得出的结果如下图：
notion image
可以看到，每一个非空节点都会对应两个子节点，那么反序列化的思路也是用队列进行层级遍历，同时用索引 index 记录对应子节点的位置：
不难发现，这个反序列化的代码逻辑也是标准的二叉树层级遍历的代码衍生出来的。我们的函数通过 nodes[index] 来计算左右子节点，接到父节点上并加入队列，一层一层地反序列化出来一棵二叉树。有点难理解，可以简单记一下思路。