广度优先遍历 BFS
解题思路
序列化：使用层序遍历将节点的值放入数组，空节点放入 null；
反序列化：迭代 list 利用层序遍历进行反序列化；
复杂度
-
时间复杂度：
O(n)，其中 n 是树的节点数；- serialize 需要
O(n)时间遍历每个点； - deserialize 需要
O(n)时间恢复每个点；
- serialize 需要
-
空间复杂度：
O(n)，其中 n 是树的节点数；- serialize 需要
O(n)空间用数组保存每个点的值； - deserialize 需要
O(n)空间用数组保存每个点的值；
- serialize 需要
代码实现
var serialize = function (root) {
if (root === null) return JSON.stringify([]);
let queue = [root];
let serializeList = [];
while (queue.length) {
let len = queue.length;
while (len--) {
// 将本次操作的结点出队
const node = queue.shift();
if (node === null) {
serializeList.push(null);
} else {
serializeList.push(node.val);
queue.push(node.left);
queue.push(node.right);
}
}
}
return JSON.stringify(serializeList);
};
var deserialize = function (list) {
list = JSON.parse(list);
if (list.length === 0) return null;
let root = new TreeNode(list[0]);
let queue = [root];
let inx = 1;
while (queue.length && inx < list.length) {
const node = queue.shift();
node.left = null;
node.right = null;
if (list[inx] !== null) {
node.left = new TreeNode(list[inx]);
queue.push(node.left);
}
inx++;
if (list[inx] !== null) {
node.right = new TreeNode(list[inx]);
queue.push(node.right);
}
inx++;
}
return root;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 173. 二叉搜索树迭代器
上一篇
评论
