题目地址
https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/
题目描述
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| 序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。
请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
示例:
你可以将以下二叉树：
1
/ \
2 3
/ \
4 5
序列化为 "[1,2,3,null,null,4,5]"
提示: 这与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。
说明: 不要使用类的成员 / 全局 / 静态变量来存储状态，你的序列化和反序列化算法应该是无状态的。
|
解题思路
序列化与反序列化成对存在，可以有不同的序列化方法，但必须通过反序列化还原成先前的数据结构或对象。
二叉树的序列化可以理解成是将二维结构转化为一维的数组或字符串，但考虑到节点的值可能为负数，数组更为合适。
本例采用前序遍历的方式，将二叉树转化为数组，其中空节点的值用‘#’代替。
本来通过前序遍历的结果是没办法还原二叉树的，至少也要前中后序遍历中的两个，但序列化后的结果包括二叉树中空指针的信息，所以反序列化是可行的。
反序列化过程也是一样，先确定根节点 root，然后遵循前序遍历的规则，递归生成左右子树。
代码实现 此例有待优化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
| javascript
/**
* 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 array = [];
function serialize1(root) {
if (!root) {
array.push('#');
return;
}
array.push(root.val);
serialize1(root.left);
serialize1(root.right);
}
serialize1(root);
return array;
};
/**
* Decodes your encoded data to tree.
*
* @param {string} data
* @return {TreeNode}
*/
var deserialize = function(data) {
function deserialize1() {
if (data === []) {
return;
}
if (data[0] === '#') {
data = data.slice(1);
return null;
}
const root = new TreeNode(data[0]);
data = data.slice(1);
root.left = deserialize1();
root.right = deserialize1();
return root;
}
return deserialize1();
};
/**
* Your functions will be called as such:
* deserialize(serialize(root));
*/
|