剑指 Offer 37. 序列化二叉树
本问题对应的 leetcode 原文链接：剑指 Offer 37. 序列化二叉树
问题描述
请实现两个函数，分别用来序列化和反序列化二叉树。
你需要设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
提示：输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。
示例：
输入：root = [1,2,3,null,null,4,5]
输出：[1,2,3,null,null,4,5]
解题思路
视频讲解直达： 本题视频讲解
代码实现
序列化：
时间复杂度：O(n)
额外空间复杂度：O(n)
反序列化：
时间复杂度：O(n)
空间复杂度：O(n)
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
// 序列化成字符串,1,2,3,null,null,4,5,null...
if(root == null){
return "";
}
StringBuilder build = new StringBuilder();
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()){
TreeNode t = queue.poll();
if(t != null){
queue.add(t.left);
queue.add(t.right);
build.append(t.val + ",");
}else{
build.append("null,");
}
}
return build.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
// 1,2,3,null,null,4,5,null...
if(data == null || data.length() <= 0){
return null;
}
String[] s = data.split(",");
Queue<TreeNode> queue = new LinkedList<>();
TreeNode root = new TreeNode(Integer.parseInt(s[0]));
queue.add(root);
int i = 1;
while(!queue.isEmpty()){
TreeNode t = queue.poll();
// 构建做左节点
if(!s[i].equals("null")){
TreeNode left = new TreeNode(Integer.parseInt(s[i]));
t.left = left;
queue.add(left);
}
i++;
// 构建右节点
if(!s[i].equals("null")){
TreeNode right = new TreeNode(Integer.parseInt(s[i]));
t.right = right;
queue.add(right);
}
i++;
}
return root;
}
}
Python
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Codec:
def serialize(self, root):
"""Encodes a tree to a single string.
:type root: TreeNode
:rtype: str
"""
if not root:
return ""
queue = []
queue.append(root)
res = []
while queue:
node = queue.pop(0)
if node:
res.append(str(node.val))
queue.append(node.left)
queue.append(node.right)
else:
res.append("null")
return ",".join(res)
def deserialize(self, data):
"""Decodes your encoded data to tree.
:type data: str
:rtype: TreeNode
"""
if not data:
return None
s = data.split(",")
queue = []
root = TreeNode(int(s[0]))
queue.append(root)
i = 1
while queue:
node = queue.pop(0)
if s[i] != "null":
left = TreeNode(int(s[i]))
node.left = left
queue.append(left)
i += 1
if s[i] != "null":
right = TreeNode(int(s[i]))
node.right = right
queue.append(right)
i += 1
return root
C++
class Codec {
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
if(root == nullptr){
return "";
}
stringstream ss;
queue<TreeNode*> q{{root}};
while(!q.empty()){
int n = q.size();
for(int i = 0; i < n; i++){
auto t = q.front(); q.pop();
if(t){
ss << t->val << ",";
q.push(t->left);
q.push(t->right);
}else{
ss << "null,";
}
}
}
string str = ss.str();
return str.substr(0, str.length() - 1);
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
if(data.empty()){
return nullptr;
}
vector<string> nodes;
stringstream ssin(data);
string token;
while(getline(ssin, token, ',')){
nodes.push_back(token);
}
TreeNode* root = new TreeNode(atoi(nodes[0].c_str()));
queue<TreeNode*> q{{root}};
int i = 1;
while(!q.empty() && i < nodes.size()){
auto t = q.front(); q.pop();
if(nodes[i] != "null"){
t->left = new TreeNode(atoi(nodes[i].c_str()));
q.push(t->left);
}
i++;
if(i < nodes.size() && nodes[i] != "null"){
t->right = new TreeNode(atoi(nodes[i].c_str()));
q.push(t->right);
}
i++;
}
return root;
}
};
JS
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* Encodes a tree to a single string.
*
* @param {TreeNode} root
* @return {string}
*/
var serialize = function (root) {
// 序列化成字符串,1,2,3,null,null,4,5,null...
if (root == null) {
return '';
}
var build = '';
var queue = [];
queue.push(root);
while (queue.length !== 0) {
var t = queue.shift();
if (t != null) {
queue.push(t.left);
queue.push(t.right);
build += t.val + ',';
} else {
build += 'null,';
}
}
return build;
};
/**
* Decodes your encoded data to tree.
*
* @param {string} data
* @return {TreeNode}
*/
var deserialize = function (data) {
// 1,2,3,null,null,4,5,null...
if (data == null || data.length <= 0) {
return null;
}
var s = data.split(',');
var queue = [];
var root = new TreeNode(parseInt(s[0]));
queue.push(root);
var i = 1;
while (queue.length !== 0) {
var t = queue.shift();
// 构建左节点
if (s[i] !== 'null') {
var left = new TreeNode(parseInt(s[i]));
t.left = left;
queue.push(left);
}
i++;
// 构建右节点
if (s[i] !== 'null') {
var right = new TreeNode(parseInt(s[i]));
t.right = right;
queue.push(right);
}
i++;
}
return root;
};
/**
* Your functions will be called as such:
* deserialize(serialize(root));
*/