剑指 Offer 37. 序列化二叉树-困难

难度：困难

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

示例：

解题思路：
初始化字符串 res
初始化队列 queue，将 root 放入队列
检查队列是否为空：
队列不为空：取出队首节点，如果节点为 null，那么 res 更新为 res + ‘#,’；如果节点不是 null，那么 res 更新为 res + val，并且将节点的左右节点依次加入 queue。继续循环。
队列为空：结束循环
返回”[“ + res + “]”

var serialize = function(root) {
    if (!root) {
        return "[]";
    }
    let res = "";
    let node = root;
    const queue = [node];
    while (queue.length) {
        const front = queue.shift();
        if (front) {
            res += `${front.val},`;
            queue.push(front.left);
            queue.push(front.right);
        } else {
            res += "#,";
        }
    }
    res = res.substring(0, res.length - 1); // 去掉最后一个逗号
    return `[${res}]`;
};

反序列化
反序列化流程如下：

去掉字符串 res 前后的[和]，并将其按照,逗号切分得到数组 nodes
初始化队列 queue，放入 nodes 的第一个值对应的节点，nodes 弹出第一个值
检查队列是否为空：
队列不为空。从 queue 取出队首元素。从 nodes 中取出第一个值和第二值，依次处理。继续循环。
队列为空。结束循环。
返回根节点。

var deserialize = function(data) {
    if (data.length <= 2) {
        return null;
    }

    const nodes = data.substring(1, data.length - 1).split(",");
    const root = new TreeNode(parseInt(nodes[0]));
    nodes.shift();

    const queue = [root];
    while (queue.length) {
        const node = queue.shift();
        // 第一个是左节点，节点为空，直接跳过
        const leftVal = nodes.shift();
        if (leftVal !== "#") {
            node.left = new TreeNode(leftVal);
            queue.push(node.left);
        }
        // 第二个是右节点，节点为空，直接跳过
        const rightVal = nodes.shift();
        if (rightVal !== "#") {
            node.right = new TreeNode(rightVal);
            queue.push(node.right);
        }
    }

    return root;
};