LeetCode题解:297. 二叉树的序列化与反序列化,DFS,JavaScript,详细注释
chencl1986 opened this issue · 0 comments
chencl1986 commented
原题链接:https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/
解题思路:
- 参考了『手画图解』剖析DFS、BFS解法 | 二叉树的序列化与反序列化。
- 该题实际上并没有严格的要求将二叉树序列化为
[1,2,3,null,null,4,5]
的形式,只要能够输出为1,2,X,X,3,4,X,X,5,X,X
(X表示节点为null),并且重新反序列化为二叉树即可。 - 序列化:
- 使用DFS遍历每个节点。
- 如果遇到节点为空,则返回X。
- 如果节点有值,则将其和左右子树,按照根、左、右的顺序拼接成字符串。
- 反序列化:
- 由于已经按照根、左、右的顺序,对二叉树进行了序列化,只要按照这个顺序递归生成二叉树即可。
- 将序列化的字符串转换成数组,每次递归都出队一个值,就保证了根、左、右的顺序。
- 如果出队的值为X,则生成一个null,并将其返回。
- 如果出队的是正常值,则用其创建一个节点,并将其与递归生成的左右子树连接成二叉树。
/**
* 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) {
return 'X';
}
// 每次递归都获取左右子树的序列化结果
const left = serialize(root.left);
const right = serialize(root.right);
// 将当前二叉树按照根,左,右的方式拼接
return `${root.val},${left},${right}`;
};
/**
* Decodes your encoded data to tree.
*
* @param {string} data
* @return {TreeNode}
*/
var deserialize = function(data) {
// 将序列化的字符串,转换为数组
const valList = data.split(',');
// 生成二叉树的方法
function build() {
// 由于二叉树已经按照根、左、右的顺序序列化,每次递归只需要按顺序取出每个节点的值即可
const val = valList.shift();
// 如果当前值为X,表示此节点为空,直接返回null
if (val === 'X') {
return null;
}
// 使用当前值生成一个节点
const node = new TreeNode(val);
// 由于子节点都是按照先左后右的顺序取出,因此按照同样顺序将子节点连接到根节点即可
node.left = build();
node.right = build();
// 将当前生成的节点返回,供上一层递归生成树
return node;
}
return build();
};