二叉树的序列化与反序列化（ LeetCode 297 ）
一、题目描述
请实现两个函数，分别用来序列化和反序列化二叉树。
你需要设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
示例 1：
输入：root = [1,2,3,null,null,4,5]
输出：[1,2,3,null,null,4,5]
示例 2：
输入：root = []
输出：[]
提示：
- 树中节点数范围是
[0, 10^4] - -1000 <= Node.val <= 1000
二、题目解析
很多同学认为这道题目难，要么是因为题目一时没看明白，要么是其他人的题解分析写的太复杂、太深奥，自己一看误以为就是一道高难度的题目。
实际上这道题目不难！
一开始，我们先来解释序列化和反序列化，这两个词的概念程序员应该不会陌生，无论你是做哪方面的开发，基本上都用到过这两个操作，简单来说就是把对象转换位另外一种方便存储或者传输的形式状态，使用的时候再把该状态逆转回来。
这道题目的意思就是要我们把二叉树通过某个手段变成一个字符串的形式，同时字符串能通过另外一种手段复原为之前的二叉树，也就是说二叉树和字符串是一一对应的关系！
理解清楚题意实际上思路也就有了。
首先，思考二叉树有哪些遍历方式。
前序、中序、后序、层序。
通过这些方式都可以把二叉树转换为数组的形式，但都存在一个问题，不同的二叉树使用不同的遍历方式会生成一个相同的数组。
所以，接下来我们的思考方式就是采取哪种方式+某种手段可以生成一个特点的数组。
直接说答案：把 null 节点放进去，所有的二叉树都变成完全二叉树！
序列化过程：
- 使用广度优先搜索按照层次的顺序从上到下遍历所有的节点
- 如果当前节点不为空，以字符串的形式打印出当前节点的值，同时把它的左右子节点加入到队列中
- 如果当前节点为空，直接打印字符串
null
反序列化过程：
- 先构造出
root入队，即字符串的第一个元素为root - 队列元素依次出队，构建当前元素的左右子节点，记为
node - 遍历字符串，如果元素不为空，放入到队列中；如果元素为 null，设置为
node的左右子节点 - 队列中的元素依次出队，设置为
node的左右子节点
三、参考代码
1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 二叉树的序列化与反序列化（ LeetCode 297 ）:https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/
public class Codec {
public String serialize(TreeNode root) {
// 边界条件处理
if(root == null) return "[]";
// 题目要求序列化后的字符串开头为 [ ,所以初始化 res 为 [
StringBuilder res = new StringBuilder("[");
// 生成一个队列，用来存储二叉树中的元素
Queue<TreeNode> queue = new LinkedList<>();
// 首先让二叉树的根节点入队
queue.add(root);
// 遍历队列，直到队列为空，说明访问了二叉树所有的元素
while(!queue.isEmpty()) {
// 队列的队首元素出队
TreeNode node = queue.poll();
// 如果出队的元素不为空，把它加入到序列化字符串 res 中，并以逗号结尾
if(node != null) {
// 加入到 res 中，以逗号结尾
res.append(node.val + ",");
// 在队列中添加当前元素的左节点
queue.add(node.left);
// 在队列中添加当前元素的右节点
queue.add(node.right);
}else {
// 如果出队的元素为空，则把 null 加入到序列化字符串 res 中，并以逗号结尾
// 这样无论输入的是什么样的二叉树，最终都变成了一颗完全二叉树
res.append("null,");
}
}
// 由于上述的遍历中的每次操作都以逗号结尾，所以此时先需要删除掉最后一个逗号
// [ 1 , 2 , 3 , ----> [ 1 , 2 , 3
res.deleteCharAt(res.length() - 1);
// 序列化字符串 res 以 ] 结尾
// [ 1 , 2 , 3 ----> [ 1 , 2 , 3 ]
res.append("]");
// 返回序列化的结果
return res.toString();
}
public TreeNode deserialize(String data) {
// 边界情况判断
if(data.equals("[]")) return null;
// 把一个字符串分割成字符串数组，同时删除了 [ 和 ]
// [1,2,3] --> 1 2 3
String[] vals = data.substring(1, data.length() - 1).split(",");
// 二叉树的根节点为字符串的第一个元素，以此构建二叉树
TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
// 辅助队列
Queue<TreeNode> queue = new LinkedList<>();
// 将根节点入队
queue.add(root);
// 设置一个索引，代表二叉树中的节点在字符串中的位置
// 由于 root 已经入队，所以索引从 1 开始
int index = 1;
// 遍历队列，直到队列为空，说明访问了数组中的所有元素
while(!queue.isEmpty()) {
// 入队
TreeNode node = queue.poll();
// 如果字符串数组中当前索引元素不为 null，则设置为当前出队节点的左子节点
if(!vals[index].equals("null")) {
// 设置为当前出队节点的左子节点
node.left = new TreeNode(Integer.parseInt(vals[index]));
// 同时，把当前索引的节点入队
queue.add(node.left);
}
// 无论字符串数组中当前索引元素是否为 null，这个元素都已经被操作了，索引向前移动，判断下一个索引元素
index++;
// 如果字符串数组中当前索引元素不为 null，则设置为当前出队节点的右子节点
if(!vals[index].equals("null")) {
// 设置为当前出队节点的右子节点
node.right = new TreeNode(Integer.parseInt(vals[index]));
// 同时，把当前索引的节点入队
queue.add(node.right);
}
// 无论字符串数组中当前索引元素是否为 null，这个元素都已经被操作了，索引向前移动，判断下一个索引元素
index++;
}
// 返回二叉树的根节点
return root;
}
}
2、C++ 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 序列化和反序列化二叉搜索树（ LeetCode 449 ）:https://leetcode-cn.com/problems/serialize-and-deserialize-bst/
class Codec
{
public:
string serialize(TreeNode *root)
{
// 边界条件处理
if (root == NULL)
return "[]";
// 题目要求序列化后的字符串开头为 [ ,所以初始化 res 为 [
string res = "[";
// 生成一个队列，用来存储二叉树中的元素
queue<TreeNode *> myqueue;
// 首先让二叉树的根节点入队
myqueue.push(root);
// 遍历队列，直到队列为空，说明访问了二叉树所有的元素
while (!myqueue.empty())
{
// 队列的队首元素出队
TreeNode *node = myqueue.front();
myqueue.pop();
// 如果出队的元素不为空，把它加入到序列化字符串 res 中，并以逗号结尾
if (node != NULL)
{
// 加入到 res 中，以逗号结尾
res.append(to_string(node->val) + ",");
// 在队列中添加当前元素的左节点
myqueue.push(node->left);
// 在队列中添加当前元素的右节点
myqueue.push(node->right);
}
else
{
// 如果出队的元素为空，则把 null 加入到序列化字符串 res 中，并以逗号结尾
// 这样无论输入的是什么样的二叉树，最终都变成了一颗完全二叉树
res.append("null,");
}
}
// 由于上述的遍历中的每次操作都以逗号结尾，所以此时先需要删除掉最后一个逗号
// [ 1 , 2 , 3 , ----> [ 1 , 2 , 3
res = res.substr(0, res.size() - 1);
// 序列化字符串 res 以 ] 结尾
// [ 1 , 2 , 3 ----> [ 1 , 2 , 3 ]
res.append("]");
// 返回序列化的结果
return res;
}
TreeNode *deserialize(string data)
{
// 边界情况判断
if (data == "[]")
return NULL;
// 把一个字符串分割成字符串数组，同时删除了 [ 和 ]
// [1,2,3] --> 1 2 3
//手动过滤字符 过滤范围为[1, data.size()-2],因为data[0] = '['data[data.size()-1] = ']'
//所以只需要过滤范围内的','即可
vector<string> vals;
for (int i = 1; i < data.size() - 1; i++)
{
string s = "";
while (i < data.size() - 1 && data[i] != ',')
{
s = s + data[i];
i++;
}
if (s != "")
vals.push_back(s);
}
// 二叉树的根节点为字符串的第一个元素，以此构建二叉树
TreeNode *root = new TreeNode(stoi(vals[0]));
// 辅助队列
queue<TreeNode *> myqueue;
// 将根节点入队
myqueue.push(root);
// 设置一个索引，代表二叉树中的节点在字符串中的位置
// 由于 root 已经入队，所以索引从 1 开始
int index = 1;
// 遍历队列，直到队列为空，说明访问了数组中的所有元素
while (!myqueue.empty() && index < vals.size())
{
// 入队
TreeNode *node = myqueue.front();
myqueue.pop();
// 如果字符串数组中当前索引元素不为 null，则设置为当前出队节点的左子节点
if (index < vals.size() && vals[index] != "null")
{
// 设置为当前出队节点的左子节点
//stoi: stringToInt std中定义的字符串类型转化成int类型的方法
node->left = new TreeNode(stoi(vals[index]));
// 同时，把当前索引的节点入队
myqueue.push(node->left);
}
// 无论字符串数组中当前索引元素是否为 null，这个元素都已经被操作了，索引向前移动，判断下一个索引元素
index++;
// 如果字符串数组中当前索引元素不为 null，则设置为当前出队节点的右子节点
if (index < vals.size() && vals[index] != "null")
{
// 设置为当前出队节点的右子节点
//stoi: stringToInt std中定义的字符串类型转化成int类型的方法
node->right = new TreeNode(stoi(vals[index]));
// 同时，把当前索引的节点入队
myqueue.push(node->right);
// 无论字符串数组中当前索引元素是否为 null，这个元素都已经被操作了，索引向前移动，判断下一个索引元素
}
index++;
}
// 返回二叉树的根节点
return root;
}
};
3、Python 代码
# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者：程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 二叉树的序列化与反序列化（ LeetCode 297 ）:https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/
class Codec:
def serialize(self, root):
# 边界条件处理
if not root :
return ""
res = []
# 生成一个队列，用来存储二叉树中的元素
queue = collections.deque()
# 首先让二叉树的根节点入队
queue.append(root)
# 遍历队列，直到队列为空，说明访问了二叉树所有的元素
while queue:
# 队列的队首元素出队
node = queue.popleft()
# 如果出队的元素不为空，把它加入到序列化字符串 res 中，并以逗号结尾
if node :
# 加入到 res 中，以逗号结尾
res.append(str(node.val))
# 在队列中添加当前元素的左节点
queue.append(node.left)
# 在队列中添加当前元素的右节点
queue.append(node.right)
else :
# 如果出队的元素为空，则把 null 加入到序列化字符串 res 中，并以逗号结尾
# 这样无论输入的是什么样的二叉树，最终都变成了一颗完全二叉树
res.append("None")
return '[' + ','.join(res) + ']'
def deserialize(self, data):
# 边界情况判断
if not data:
return []
# 把一个字符串分割成字符串数组，同时删除了 [ 和 ]
# [1,2,3] --> 1 2 3
vals = data[1:-1].split(',')
# 二叉树的根节点为字符串的第一个元素，以此构建二叉树
root = TreeNode(int(vals[0]))
# 辅助队列
queue = collections.deque()
# 将根节点入队
queue.append(root)
# 设置一个索引，代表二叉树中的节点在字符串中的位置
# 由于 root 已经入队，所以索引从 1 开始
index = 1
# 遍历队列，直到队列为空，说明访问了数组中的所有元素
while queue :
# 入队
node = queue.popleft()
# 如果字符串数组中当前索引元素不为 null，则设置为当前出队节点的左子节点
if vals[index] != 'None':
# 设置为当前出队节点的左子节点
node.left = TreeNode(int(vals[index]))
# 同时，把当前索引的节点入队
queue.append(node.left)
# 无论字符串数组中当前索引元素是否为 null，这个元素都已经被操作了，索引向前移动，判断下一个索引元素
index += 1
# 如果字符串数组中当前索引元素不为 null，则设置为当前出队节点的右子节点
if vals[index] != 'None':
# 设置为当前出队节点的右子节点
node.right = TreeNode(int(vals[index]))
# 同时，把当前索引的节点入队
queue.append(node.right)
# 无论字符串数组中当前索引元素是否为 null，这个元素都已经被操作了，索引向前移动，判断下一个索引元素
index += 1
# 返回二叉树的根节点
return root
