要重构一棵二叉树的话，只要把原二叉树的结构记录下来就好了。
序列化时可以用层级遍历来记录树的结构，记得把空节点也记录下来。
反序列化时也是用层级遍历的方法一层一层地垒节点就好啦。
/**
* 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:
string empty_node = "#";
string delimeter = ",";
string end_of_level = ";";
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
if (!root) return string();
string serialized_string;
queue<TreeNode*> q;
q.push(root);
// 平平无奇的层级遍历
while (!q.empty()) {
int size = q.size();
while (size--) {
TreeNode* node = q.front(); q.pop();
if (node) {
serialized_string += to_string(node->val);
q.push(node->left);
q.push(node->right);
} else {
// 记录空节点
serialized_string += empty_node;
}
// 分割节点
serialized_string += delimeter;
}
}
return serialized_string;
}
TreeNode* makeTreeNode(const string& data, int& pos) {
// 读取下一个分隔记号(",")前的数字
string::size_type delim = data.find(delimeter, pos);
string val = data.substr(pos, delim - pos);
pos = delim + 1;
if (val.compare(empty_node) == 0)
return nullptr;
return new TreeNode(stoi(val));
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
if (data.empty()) return nullptr;
int i = 0;
TreeNode* root = makeTreeNode(data, i);
queue<TreeNode*> q;
q.push(root);
// 先构造个根节点，接下来又是平平无奇的层级遍历
while (!q.empty()) {
int size = q.size();
while (size--) {
TreeNode* node = q.front(); q.pop();
node->left = makeTreeNode(data, i);
node->right = makeTreeNode(data, i);
if (node->left)
q.push(node->left);
if (node->right)
q.push(node->right);
}
}
return root;
}
};
// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(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, emptyMarker = '#', seperator = ',') {
if (!root) return '';
const queue = [root];
const arr = [];
// BFS
while (queue.length) {
const node = queue.shift();
if (node) {
arr.push(node.val);
// 子节点为空也要入列，因为要标记空节点
queue.push(node.left, node.right);
} else {
// 标记空节点
arr.push(emptyMarker);
}
}
// 最后一层右侧的那些空节点标记可以删掉
// 不删也行 `return arr.join(seperator);`
return arr
.join(seperator)
.replace(new RegExp(`(${seperator}${emptyMarker})+$`), '');
};
/**
* Decodes your encoded data to tree.
*
* @param {string} data
* @return {TreeNode}
*/
var deserialize = function (data, emptyMarker = '#', seperator = ',') {
if (!data) return null;
const nodes = data.split(seperator);
const root = new TreeNode(nodes[0]);
const queue = [root];
let i = 1;
// BFS
while (queue.length) {
const node = queue.shift();
node.left = buildNode(nodes[i]);
node.left && queue.push(node.left);
i++;
node.right = buildNode(nodes[i]);
node.right && queue.push(node.right);
i++;
}
return root;
// *********************************
function buildNode(value) {
return value === void 0 || value === emptyMarker
? null
: new TreeNode(value);
}
};
/**
* Your functions will be called as such:
* deserialize(serialize(root));
*/
deserialize() 也可以用正则来读取节点值。
/**
* Decodes your encoded data to tree.
*
* @param {string} data
* @return {TreeNode}
*/
var deserialize = function (data, emptyMarker = '#', seperator = ',') {
const reg = new RegExp(`[^${seperator}]+`, 'g');
let match = reg.exec(data);
if (!match) return null;
const root = new TreeNode(match[0]);
const queue = [root];
while (queue.length) {
const node = queue.shift();
match = reg.exec(data);
if (!match) break;
node.left = buildNode(match[0]);
node.left && queue.push(node.left);
match = reg.exec(data);
if (!match) break;
node.right = buildNode(match[0]);
node.right && queue.push(node.right);
}
return root;
// *********************************
function buildNode(value) {
return value === emptyMarker ? null : new TreeNode(value);
}
};
serialize()
deserialize()
nodes 来存所有节点的值，层次遍历时用的队列空间是 q，最差情况也是与 N 同阶。这里用的是 preorder。
serialize
正常前序遍历即可，在遍历过程中组装字符串，遇到空节点加一个标识符。