序列化二叉树 🌟🌟🌟困难
课后作业
问题描述
原文链接：剑指 Offer 37. 序列化二叉树
请实现两个函数，分别用来序列化和反序列化二叉树。
你需要设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
提示：输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。
示例：
输入：root = [1,2,3,null,null,4,5]
输出：[1,2,3,null,null,4,5]
代码实现
Java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
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;
}
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(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 ""
s = [str(root.val)]
queue = [root]
while queue:
node = queue.pop(0)
if node.left:
s.append(str(node.left.val))
queue.append(node.left)
else:
s.append("null")
if node.right:
s.append(str(node.right.val))
queue.append(node.right)
else:
s.append("null")
return ",".join(s)
def deserialize(self, data):
"""Decodes your encoded data to tree.
:type data: str
:rtype: TreeNode
"""
if not data:
return None
s = data.split(",")
root = TreeNode(int(s[0]))
queue = [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++
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Codec {
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
// 序列化成字符串,1,2,3,null,null,4,5,null...
if(!root) {
return "";
}
stringstream ss;
queue<TreeNode*> q;
q.push(root);
while(!q.empty()) {
TreeNode* t = q.front();
q.pop();
if(t) {
q.push(t->left);
q.push(t->right);
ss << t->val << ",";
}
else {
ss << "null,";
}
}
string s = ss.str();
return s.substr(0, s.size() - 1);
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
// 1,2,3,null,null,4,5,null...
if(data.empty()) {
return nullptr;
}
vector<string> s;
stringstream ss(data);
string str;
while(getline(ss, str, ',')) {
s.push_back(str);
}
queue<TreeNode*> q;
TreeNode* root = new TreeNode(stoi(s[0]));
q.push(root);
int i = 1;
while(!q.empty()) {
TreeNode* t = q.front();
q.pop();
// 构建左节点
if(s[i] != "null") {
TreeNode* left = new TreeNode(stoi(s[i]));
t->left = left;
q.push(left);
}
i++;
// 构建右节点
if(s[i] != "null") {
TreeNode* right = new TreeNode(stoi(s[i]));
t->right = right;
q.push(right);
}
i++;
}
return root;
}
};
// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));
