题目描述：

请实现两个函数，分别用来序列化和反序列化二叉树
二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#），以 ！ 表示一个结点值的结束（value!）。

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

例如，我们可以把一个只有根节点为1的二叉树序列化为”1,”，然后通过自己的函数来解析回这个二叉树

知识点：

  • 广度优先遍历

解题思路：

  • 这道题要求我们将一棵树转换为字符串，之后将这个字符串还原为树

首先我们来看序列化：

  • 我们将二叉树的所有节点值转换为字符串，并以 ! 来分割，如果遇见空字符我们将其用#来表示
  • 以 ！分割的目的是为后序转换为树的时候方便
  • 这道题我使用的广度优先遍历，按道理其他优先遍历也是可以的，注意的是如果是按照广度优先转换为字符串的那么我们也要按照广度优先还原
  • 但是在此题中我们的广度优先遍历是不需要考虑判断当前节点是否存在的，如果遇到不存在的情况我们直接转换为#便好

解题代码：

  1. function Serialize(pRoot)
  2. {
  3.     // write code here
  4.     if(!pRoot) return '[]';
  5.     let res = '';
  6.     const queue = [pRoot];
  7.     while(queue.length) {
  8.         let temp = queue.shift();
  9.         if(temp) {
  10.             res += `${temp.val}!`;
  11.             queue.push(temp.left);
  12.             queue.push(temp.right);
  13.         }else {
  14.             res += '#!'; // 处理空节点的情况
  15.         }
  16.     }
  17.     // 去掉末尾的!
  18.     res = res.slice(0,res.length - 1);
  19.     return `[${res}]`;
  20. }

其次是反序列化：

  • 在获得上面传递的字符串之后我们需要的是首先将其边界处的两端去掉
  • 之后将这个字符串通过 ! 分割为队列，这样问题就变得简单了
  • 首先我们需要通过队列的第一个元素创建根节点（先序遍历的第一个节点为根节点）
  • 之后再创建一个队列用于该树的广度优先遍历（即按广度优先的顺序来重建这棵二叉树）
  • 最后返回根节点

解题代码：

function Deserialize(s)
{
    // write code here
    if(s.length <= 2) return null;
    // 记得，split是将字符串转换为数组，join是将数组转换为字符串
    const nodes = s.slice(1,s.length-1).split('!');
    const root = new TreeNode(parseInt(nodes.shift()));
    const queue = [root];
    while (queue.length) {
        let temp = queue.shift();
        let leftVal = nodes.shift();
        if(leftVal !== '#') {
            temp.left = new TreeNode(parseInt(leftVal));
            queue.push(temp.left);
        }
        let rightVal = nodes.shift();
        if(rightVal !== '#') {
            temp.right = new TreeNode(parseInt(rightVal));
            queue.push(temp.right);
        }
    }
    return root;
}