序列化二叉树
请实现两个函数，分别用来序列化和反序列化二叉树。
示例:
你可以将以下二叉树：
1
/ \
2 3
/ \
4 5
序列化为 "[1,2,3,null,null,4,5]"
思路
1 利用层序遍历，序列化二叉树
2 通用利用层序遍历，反序列化二叉树
代码
/**
* 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) {
// };
function serialize(root) {
const res = [];
const queue = [root];
while (queue.length > 0) {
const node = queue.shift();
if (node) {
res.push(node.val);
queue.push(node.left);
queue.push(node.right);
} else {
res.push('X');
}
}
return res.join(',');
}
/**
* Decodes your encoded data to tree.
*
* @param {string} data
* @return {TreeNode}
*/
var deserialize = function(data) {
if (data === 'X') {
return null;
}
const vals = data.split(",");
const root = new TreeNode(vals[0]);
const queue = [root];
let i = 1;
while (i < vals.length) {
const node = queue.shift();
if (vals[i] !== 'X') {
node.left = new TreeNode(vals[i]);
queue.push(node.left);
}
i++;
if (vals[i] !== 'X') {
node.right = new TreeNode(vals[i]);
queue.push(node.right);
}
i++;
}
return root;
};
/**
* Your functions will be called as such:
* deserialize(serialize(root));
*/
复杂度分析
- 时间复杂度: O(N)
- 空间复杂度: O(N)