剑指Offer题解 - Day62

chuckQu

发布于 2022-08-19 11:07:07

970

发布于 2022-08-19 11:07:07

文章被收录于专栏：前端F2E

剑指 Offer 37. 序列化二叉树

力扣题目链接[1]

请实现两个函数，分别用来序列化和反序列化二叉树。

你需要设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

提示：输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。

示例：

输入：root = [1,2,3,null,null,4,5]
输出：[1,2,3,null,null,4,5]

思路：

按照题目描述，可以总结出：

序列化和反序列化是可逆操作，因此需要携带完整的二叉树信息，包括空节点。
打印出的二叉树信息是层序遍历的结果，而层序遍历需要使用队列来实现。

因此，核心问题就来到了如何完整的打印出二叉树？

相较于普通的二叉树打印，此题多了额外一步，就是当前节点为空时，需要将null存储到结果数组中。

首先先看下完整的代码：

BFS

/**
 * Encodes a tree to a single string.
 *
 * @param {TreeNode} root
 * @return {string}
 */
var serialize = function(root) {
    if(!root) return '[]'; // 二叉树为空，返回'[]'
    let queue = [root]; // 广度优先遍历逻辑
    let res = [];
    while(queue.length) {
        const node = queue.shift();
        if (node) {
            res.push(node.val);
            queue.push(node.left, node.right);
        } else {
            res.push(null); // 节点为空，插入null
        }
    }
    return JSON.stringify(res); // 返回序列化的结果数组
};

/**
 * Decodes your encoded data to tree.
 *
 * @param {string} data
 * @return {TreeNode}
 */
var deserialize = function(data) {
    if (data === '[]') return null;
    let valList = data.slice(1, -1).split(','); // 去除'['和']'，并转换为数组
    let root = new TreeNode(+valList[0]); // 初始化根节点
    let queue = [root]; // 按照BFS方式遍历valList
    let i = 1;
    while(queue.length) {
        let node = queue.shift();
        if (valList[i] !== 'null') {
            node.left = new TreeNode(+valList[i])
            queue.push(node.left);
        }
        i++;
        if (valList[i] !== 'null') {
            node.right = new TreeNode(+valList[i]);
            queue.push(node.right);
        }
        i++;
    }
    return root;
};