/**
* 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) {
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;
}
};
// Your Codec objectwill be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));
思路:层序遍历，空节点使用null表示
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
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) {
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;
}
}
/**
* 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) { //层序遍历，放入字符串中
let res = ""
if (root == null) {
return res
}
let queue = [root]
while (queue.length > 0) {
let node = queue.shift()
if (node) {
queue.push(node.left)
queue.push(node.right)
res += node.val + ',' //， 用来分隔
} else {
res += "null,"
}
}
return res
};
/**
* Decodes your encoded data to tree.
*
* @param {string} data
* @return {TreeNode}
*/
var deserialize = function (data) {
if (data.length <= 0 || data == null) return null
let res = data.split(',');
let root = new TreeNode(Number(res[0]))
let queue = [root]
let i = 1 //记录res中的下标，对应每个节点，
while (queue.length > 0) {
let node = queue.shift()
if (res[i] != 'null') { //一个节点有俩子节点，故加两次，到下一个节点
let left = new TreeNode(Number(res[i++])) //弹出节点的左节点
node.left = left
queue.push(left)
}
if (res[i] != 'null') {
let right = new TreeNode(Number(res[i++]))
node.right = right
queue.push(right)
}
}
return root
};
/**
* Your functions will be called as such:
* deserialize(serialize(root));
*/
shuaidi
共以下 18 个回答
public class Codec {
}
思路：使用队列+层序遍历
“`c++
class Codec {
public:
};
“`
class Codec {
public:
void rserialize(TreeNode* root, string& str) {
if (root nullptr) {
str += “None,”;
} else {
str += to_string(root->val) + “,”;
rserialize(root->left, str);
rserialize(root->right, str);
}
}
};
时空复杂度O(n)
/**
* 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) {
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);
}
};
// Your Codec objectwill be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));
思路:层序遍历，空节点使用null表示
序列化：
时间复杂度：O(n)
额外空间复杂度：O(n)
反序列化：
时间复杂度：O(n)
空间复杂度：O(n)
java
public class Codec {
}
提交
序列化和反序列化的时间复杂度和空间复杂度都为O(n)
层次遍历：
时空复杂度都是O（n）
这题有点难了，明天再来一遍
class Codec {
public:
};
day11第一题
用层序遍历实现序列化和反序列化，时间复杂度和空间复杂度都和层序遍历相同，$O(n)$
public class Codec {
}
//层序遍历
//时空复杂度均为On
最后一次打卡二叉树，吃透了一下别人的代码
本来是想用前序+中序遍历加密，然后用之前的重建二叉树解码，结果它里面包含重复元素使我的哈希表失效
只能用官方的前序遍历+记录none节点的方法解题了
时间复杂度O(n)
空间复杂度O(n)
“`C++
class Codec {
public:
private:
//前序遍历
void serialize_f(TreeNode* root, string& str)
{
if(root nullptr)
{
str += “none,”;
return;
}
};
“`
打卡