描述

请实现两个函数，分别用来序列化和反序列化二叉树，不对序列化之后的字符串进行约束，但要求能够根据序列化之后的字符串重新构造出一棵与原二叉树相同的树。

二叉树的序列化(Serialize)是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树等遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#）

二叉树的反序列化(Deserialize)是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。

例如，可以根据层序遍历的方案序列化，如下图:

    1
   / \
  2   3
     / \
    6   7

层序序列化(即用函数Serialize转化)如上的二叉树转为"{1, 2, 3, #, #, 6, 7}"，再能够调用反序列化(Deserialize)将"{1, 2, 3, #, #, 6, 7}"构造成如上的二叉树。

再举一个例子

       5
      /
     4
    /
   3  
  /
 2

层序序列化(即用函数Serialize转化)如上的二叉树转为"{5, 4, #, 3, #, 2}"，再能够调用反序列化(Deserialize)将"{5, 4, #, 3, #, 2}构造成如上的二叉树。

当然你也可以根据满二叉树结点位置的标号规律来序列化，还可以根据先序遍历和中序遍历的结果来序列化。不对序列化之后的字符串进行约束，所以欢迎各种奇思妙想。

链接

BM39 序列化二叉树 Nowcoder

示例

输入：{1,2,3,#,#,6,7}
返回值：{1,2,3,#,#,6,7}

输入：{8,6,10,5,7,9,11}
返回值：{8,6,10,5,7,9,11}

题解

在JavaScript中，序列化和反序列化二叉树采用层次遍历（BFS）实现。核心思想是将二叉树转换为字符串（序列化），再从字符串还原树结构（反序列化）。

/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function Serialize(pRoot) {
    // write code here
    let queue = [pRoot];
    let res = [];

    while (queue.length) {
        const node = queue.shift();
        if (node) {
            res.push(node.val);
            queue.push(node.left);
            queue.push(node.right);
        } else {
            res.push("#");
        }
    }

    // 删除尾部多余的 #
    while (res.length && res[res.length - 1] === "#") {
        res.pop();
    }

    return res.join(",");
}

function Deserialize(s) {
    console.log(s);
    if (!s) return null
    arr = s.split(',')
    // write code here
    if (arr.length === 0) return null;
    const root = {
        val: arr[0],
        left: null,
        right: null
    };
    const queue = [root];
    let index = 1;
    while (queue.length && index < arr.length) {
        const node = queue.shift();
        if (arr[index] !== "#") {
            node.left = {
                val: arr[index],
                left: null,
                right: null
            };
            queue.push(node.left);
        }
        index++;
        if (arr[index] !== "#" && index < arr.length) {
            node.right = {
                val: arr[index],
                left: null,
                right: null
            };
            queue.push(node.right);
        }
        index++;
    }

    return root;
}
module.exports = {
    Serialize: Serialize,
    Deserialize: Deserialize,
};