第 37 题：序列化二叉树
传送门：序列化二叉树，牛客网 online judge 地址。
请实现两个函数，分别用来序列化和反序列化二叉树。
您需要确保二叉树可以序列化为字符串，并且可以将此字符串反序列化为原始树结构。
样例：
你可以序列化如下的二叉树
8 / \ 12 2 / \ 6 4为：
"[8, 12, 2, null, null, 6, 4, null, null, null, null]"注意:
- 以上的格式是 AcWing 序列化二叉树的方式，你不必一定按照此格式，所以可以设计出一些新的构造方式。
分析：总之就是前序遍历。因为“前序遍历”有很好的性质：
《剑指 Offer （第 2 版）》第 37 题：序列化二叉树
说明：根据上面的序列化规则，上图中的二叉树被序列化成字符串 "1，2，4，$，$，$，3，5，$，$，6，$，$" 。
Python 代码：
class Solution:
# 前序遍历
def serialize(self, root):
"""Encodes a tree to a single string.
:type root: TreeNode
:rtype: str
"""
res = ''
if root is None:
return '! '
res += str(root.val)
res += ' '
res += self.serialize(root.left)
res += self.serialize(root.right)
return res
def deserialize(self, data):
"""Decodes your encoded data to tree.
:type data: str
:rtype: TreeNode
"""
arr = data.split(' ')
return self.__helper(arr)
def __helper(self, arr):
if arr:
top = arr.pop(0)
if top != '!':
root = TreeNode(int(top))
root.left = self.__helper(arr)
root.right = self.__helper(arr)
return root
else:
return None
Python 代码：序列化时候，不用递归，用栈的写法
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
# 前序遍历
def serialize(self, root):
"""Encodes a tree to a single string.
:type root: TreeNode
:rtype: str
"""
res = []
if root is None:
return '!'
stack = [root]
while stack:
top = stack.pop()
if top is None:
res.append('!')
else:
stack.append(top.right)
stack.append(top.left)
res.append(str(top.val))
return ' '.join(res)
def deserialize(self, data):
"""Decodes your encoded data to tree.
:type data: str
:rtype: TreeNode
"""
queue = data.split(' ')
return self.__build_tree(queue)
def __build_tree(self, queue):
if queue:
top = queue.pop(0)
if top != '!':
root = TreeNode(int(top))
root.left = self.__build_tree(queue)
root.right = self.__build_tree(queue)
return root
else:
return None
# 如果 queue 为空，就什么都不做
Java 代码：序列化：前序遍历二叉树存入字符串中，反序列化：根据前序遍历重建二叉树
import java.util.LinkedList;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
public class Solution {
/**
* 序列化一棵二叉树（其实就是前序遍历）
* @param root
* @return
*/
public String serialize(TreeNode root) {
if (root == null) {
return "$,";
}
StringBuilder sb = new StringBuilder(root.val + ",");
sb.append(serialize(root.left));
sb.append(serialize(root.right));
return sb.toString();
}
// 反序列化一棵二叉树
public TreeNode deserialize(String str) {
String[] strArr = str.split(",");
LinkedList<String> queue = new LinkedList<>();
for (String s : strArr) {
queue.addLast(s);
}
return preOrder(queue);
}
// 使用队列就实现了迭代器的功能
private TreeNode preOrder(LinkedList<String> queue) {
String s = queue.removeFirst();
if (!"$".endsWith(s)) {
TreeNode newNode = new TreeNode(Integer.parseInt(s));
newNode.left = preOrder(queue);
newNode.right = preOrder(queue);
// 理解将新创建的结点返回回去的必要性
return newNode;
}
// 是 "$" 就返回空指针，注意这里的递归方法，会把空指针接在原来的树节点上
return null;
}
}
另一种写法：
Java 代码：
import java.util.LinkedList;
// 前序遍历
public class Solution2 {
String Serialize(TreeNode root) {
StringBuilder stringBuilder = new StringBuilder();
preOrder(root, stringBuilder);
return stringBuilder.toString();
}
// 上面函数的辅助函数
private void preOrder(TreeNode node, StringBuilder stringBuilder) {
if (node == null) {
stringBuilder.append("#");
stringBuilder.append(",");
return;
}
stringBuilder.append(node.val);
stringBuilder.append(",");
preOrder(node.left, stringBuilder);
preOrder(node.right, stringBuilder);
}
TreeNode Deserialize(String str) {
String[] strings = str.split(",");
int size = strings.length;
System.out.println(size);
LinkedList<String> queue = new LinkedList<>();
for (int i = 0; i < size; i++) {
queue.addLast(strings[i]);
}
return inOrderGenerate(queue);
}
private TreeNode inOrderGenerate(LinkedList<String> queue) {
if (queue.isEmpty()) {
return null;
}
String s = queue.removeFirst();
if (!"#".equals(s)) {
TreeNode root = new TreeNode(Integer.parseInt(s));
root.left = inOrderGenerate(queue);
root.right = inOrderGenerate(queue);
return root;
}
return null;
}
}
C++ 代码：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
string res;
dfs_s(root, res);
return res;
}
void dfs_s(TreeNode *root, string &res)
{
if (!root) {
res += "null ";
return;
}
res += to_string(root->val) + ' ';
dfs_s(root->left, res);
dfs_s(root->right, res);
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
int u = 0;
return dfs_d(data, u);
}
TreeNode* dfs_d(string &data, int &u)
{
if (u == data.size()) return NULL;
int k = u;
while (data[k] != ' ') k ++ ;
if (data[u] == 'n') {
u = k + 1;
return NULL;
}
int val = 0;
for (int i = u; i < k; i ++ ) val = val * 10 + data[i] - '0';
u = k + 1;
auto root = new TreeNode(val);
root->left = dfs_d(data, u);
root->right = dfs_d(data, u);
return root;
}
};
作者：yxc
链接：https://www.acwing.com/activity/content/code/content/20710/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
