序列化二叉树
解题思路：
-
利用完全二叉树的结构来维护的一维数组，不存在的节点为 null 占位；
-
层序遍历：
- 需要借助一个队列；
- 首先将二叉树的根节点入队列，然后出队，访问该节点，如果它的左子树不空，则将左子树的根节点入队；
- 如果它的右子树不为空，则将右子树的根节点入队；
- 然后出队，对出队节点进行访问，如此反复，直到队列为空；
![]( "序列化二叉树")
-
序列化 Serialize：
- 层序遍历借助一个队列实现序列化，将根节点入队；
- 循环判断队列是否为空：
- 当队列不为空，则出队一个节点 node，将当前节点值或 null 放到结果 res 中；
- 判断 node 是否有左节点，没有则将 null 入队，有则将该节点入队；
- 判断 node 是否有右节点，没有则将 null 入队，有则将该节点入队；
- 循环往复，直到队列为空，返回一个序列化的 res；
-
反序列化 Deserialize：
i. 层序遍历借助一个队列实现反序列化；
ii. 步骤和上面类似；
复杂度：
-
时间复杂度： O(N)；
-
空间复杂度： O(N)；
代码实现：
function serialize(root: TreeNode | null): string {
if (root === null) return JSON.stringify([]);
let queue: TreeNode[] = [root];
let serializeList: number[] = [];
while (queue.length) {
let len = queue.length;
while (len > 0) {
// 将本次操作的结点出队
const node = queue.shift();
len--;
if (node === null) {
serializeList.push(null);
} else {
serializeList.push(node.val);
node.left ? queue.push(node.left) : queue.push(null);
node.right ? queue.push(node.right) : queue.push(null);
}
}
}
return JSON.stringify(serializeList);
};
function deserialize(data: string): TreeNode | null {
let list: number[] = JSON.parse(data);
if (list.length === 0) return null;
let inx: number = 1;
let root: TreeNode = new TreeNode(list[0]);
let queue = [root];
while (queue.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;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
剑指 Offer 31.栈的压入、弹出序列
上一篇
评论
