@(LeetCode)
问题描述
序列化是将数据或者对象转换为二进制的过程,因此可以被存储在文件或者内存中,或是通过网络进行传输,在同一台或者另一台电脑上可被重新恢复为原来的数据。
设计一个算法来序列化和反序列化二叉搜索树。对于算法没有任何限制。只需要保证将二叉搜索树序列化为字符串,并且该字符串可被反序列化成原先的树结构。
序列化后的字符串应该尽量紧凑。
注意:不要使用类中的成员/全局/静态变量来存储状态。序列化和反序列化应该是无状态的。
解题思路
解此题的关键是利用二叉搜索树的相关性质,即:
- 左子树的值 < 父节点的值。
- 右子树的值 > 父节点的值。
若要重建二叉搜索树,只需将节点一个个的按照规则进行插入即可。但是节点的插入顺序是影响重建的重要因素。因此,在序列化时,遍历的顺序比较重要。
其中满足条件的遍历方式有两种:
- 先序遍历
- 层遍历
至于为什么是这两种,可使用各种遍历方式自行分析一下,比较简单。
所以解题步骤如下:
- 采用先序/层遍历方式,将节点值存储下来。
- 构建二叉搜索树。根据这些节点值,不断的将其插入到二叉搜索树中。
下面给出先序遍历的解法,以 -
连接节点。
var serialize = function (root) {
if (root) {
return `-${root.val}` + serialize(root.left) + serialize(root.right)
}
return ''
};
反序列化:
var deserialize = function (data) {
let str = data
if (str && str.length > 0) {
// 去除首个 -,因为 split 后是空格
if (str.startsWith('-')) {
str = str.substring(1, str.length)
}
let array = str.split('-')
if (array.length >= 1) {
let root = null
let i = 0
while (i < array.length) {
// 将节点逐个插入
root = buildTree(root, parseInt(array[i]))
i += 1
}
return root
}
}
return null
};
// 构建树
var buildTree = function (root, val) {
if (!root) {
return new TreeNode(val)
}
if (val < root.val) {
root.left = buildTree(root.left, val)
} else {
root.right = buildTree(root.right, val)
}
return root
}
网友评论