序列化是将一个数据结构或者对象转换为连续的比特位的操作, 进而可以将转换后的数据存储在一个文件或者内存中, 同时也可以通过网络传输到另一个计算机环境,采取相反方式重构得到原数据。
请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑, 你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
你可以将以下二叉树:
1
/ \
2 3
/ \
4 5
序列化为 "[1,2,3,null,null,4,5]"
不要使用类的成员 / 全局 / 静态变量来存储状态,你的序列化和反序列化算法应该是无状态的。
官方提供的解法暂无 javascript,根据官方逻辑使用 javascript 实现:
深度优先搜索
二叉树的序列化本质上是对其值进行编码,更重要的是对其结构进行编码。可以遍历树来完成上述任务。众所周知,我们一般有两个策略:BFS / DFS。
TreeNode:val 当前指针指的值,left 上一个值,right 下一个值
/**
* 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) {
if (root === null || root.val === null) return 'null,'
return root.val + ',' + serialize(root.left) + serialize(root.right)
}
/**
* Decodes your encoded data to tree.
*
* @param {string} data
* @return {TreeNode}
*/
var deserialize = function (data) {
function tree(list) {
if (list.length === 0);
let val = list.shift()
if (val === 'null') return null
let node = new TreeNode(val)
node.left = tree(list)
node.right = tree(list)
return node
}
let list = data.split(',')
return tree(list)
}
/**
* Your functions will be called as such:
* deserialize(serialize(root));
*/
BFS
序列化 —— 常规的 BFS
反序列化——也是 BFS,父节点出列,子节点入列
同时考察父节点,和两个子节点值
/**
* Encodes a tree to a single string.
*
* @param {TreeNode} root
* @return {string}
*/
var serialize = function (root) {
const queue = [root]
let res = []
while (queue.length) {
const node = queue.shift()
if (node) {
// 出列的节点 带出子节点入列
res.push(node.val)
queue.push(node.left) // 不管是不是null节点都入列
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 // 就一个'X',只有一个null
const list = data.split(',') // 序列化字符串转成list数组
const root = new TreeNode(list[0]) //首项是根节点值,为它创建节点
const queue = [root] // 初始放入root,待会出列考察
let cursor = 1 // 从list第二项开始遍历
while (cursor < list.length) {
// 指针越界
const node = queue.shift() // 父节点出列考察
const leftVal = list[cursor] // 获取左子节点值
const rightVal = list[cursor + 1] // 获取右子节点值
if (leftVal !== 'X') {
// 左子节点值是有效值
const leftNode = new TreeNode(leftVal) // 创建节点
node.left = leftNode // 成为当前出列节点的左子节点
queue.push(leftNode) // 它是未来的爸爸,入列等待考察
}
if (rightVal !== 'X') {
// 右子节点值是有效值
const rightNode = new TreeNode(rightVal) // 创建节点
node.right = rightNode // 成为当前出列节点的右子节点
queue.push(rightNode) // 它是未来的爸爸,入列等待考察
}
cursor += 2 // 指针前进2位
}
return root // 返回根节点
}
这道题本地调试有点曲折 题目提示了:
// Definition for a binary tree node.
function TreeNode(val) {
this.val = val
this.left = this.right = null
}
// Your functions will be called as such:
deserialize(serialize(root))
但是在本地调试的时候还是有点地方要修改的: