二叉树（三）——序列化

297. 二叉树的序列化和反序列化（困难）

早安，我们一起啃下这道经典的题目。

DFS（递归）

递归遍历一棵树，只需关注当前节点就好，它的子树的遍历交给递归完成：
“serialize 函数，请帮我分别序列化我的左右子树，我等你的返回结果，再拼接一下。”

1. 选择前序遍历，是因为 根 | 左 | 右的打印顺序，在反序列化时更容易**定位出根节点的值**
2. 遇到 null 节点也要翻译成指定符号，反序列化时才知道这里是 null

序列化的代码

const serialize = (root) => {
  if (root == null) {                  // 遍历到 null 节点
    return 'X';
  }
  const left = serialize(root.left);   // 左子树的序列化结果
  const right = serialize(root.right); // 右子树的序列化结果
  return root.val + ',' + left + ','+ right; // 按  根,左,右  拼接字符串
};

反序列化 —— 也是递归

1. 前序遍历的序列化字符串，大致呈现这样的排列：

“根 |(根 |(根 | 左 | 右)|(根 | 左 | 右))|(根 |(根 | 左 | 右)|(根 | 左 | 右))”

1. 定义函数 buildTree 用于构建还原，接收由序列化字符串转成的 list 数组。

2. 逐个弹出 list 的首项（根节点值），构建当前子树的根节点，顺着 list，就会先构建根节点 > 构建左子树 > 构建右子树。

   1. 如果弹出的字符为 ‘#’，则 return null 节点。
   2. 如果弹出的字符是数值，则创建 root 节点，并递归构建 root 的左右子树，最后返回 root。

反序列化的代码

const deserialize = (data) => {
  const list = data.split(',');   // split成数组

  const buildTree = (list) => {   // 基于list构建当前子树
    const rootVal = list.shift(); // 弹出首项，获取它的“数据”
    if (rootVal == "X") {         // 是X，返回null节点
      return null;
    }
    const root = new TreeNode(rootVal); // 不是X，则创建节点
    root.left = buildTree(list);        // 递归构建左子树
    root.right = buildTree(list);       // 递归构建右子树
    return root;                        // 返回当前构建好的root
  };

  return buildTree(list); // 构建的入口
};

BFS 解法

序列化 —— 很典型的 BFS

1. 维护一个队列，初始让根节点入列，考察出列节点：
   1. 如果出列的节点是 null，将符号 ‘X’ 推入 res 数组。
   2. 如果出列的节点不是 null，将节点值推入数组 res，并将它的左右子节点入列。
      1. 注意子节点 null 也入列，它对应 “X”，需要被记录，只是它没有子节点可入列。
2. 入列、出列… 直到队列为空，所有节点遍历完，res 也好了，转成字符串就是结果。

序列化的代码

const serialize = (root) => {
  const queue = [root];
  let res = [];
  while (queue.length) {                // 循环条件
    const node = queue.shift(); // 考察出列的节点
    if (node) {                 // 是真实节点，带出子节点入列
      res.push(node.val);       // 节点值推入res
      queue.push(node.left);    // 子节点入列，不管是不是null节点都入列
      queue.push(node.right);    
    } else {                    // 是null节点，没有子节点入列
      res.push('X');            // X 推入res
    }
  }
  return res.join(',');                  // 转成字符串，并用','分隔。
}

反序列化 —— 也是 BFS
下图是 BFS 得到的序列化字符串，和 DFS 得到的不同，它是一层层的。除了第一个是根节点的值，其他节点值都是成对的，对应左右子节点。

先将序列化字符串转成数组 list，用一个指针 cursor 从第二项开始扫描。
起初，用 list[0] 构建根节点，并让根节点入列。
节点出列，此时 cursor 指向它的左子节点值，cursor+1 指向它的右子节点值。
如果子节点值是数值，则创建节点，并认出列的父亲，同时自己也是父亲，入列。
如果子节点值为 ‘X’，什么都不用做，因为出列的父亲的 left 和 right 本来就是 null
可见，所有的真实节点都会在队列里走一遍，出列就带出儿子入列

反序列化 代码

const deserialize = (data) => {
  if (data == 'X') return null;
  const list = data.split(',');  // 序列化字符串split成数组
  const root = new TreeNode(list[0]); // 获取首项，构建根节点
  const queue = [root];          // 根节点推入队列
  let cursor = 1;                // 初始指向list第二项
  while (cursor < list.length) { // 指针越界，即扫完了序列化字符串
    const node = queue.shift();  // 考察出列的节点
    const leftVal = list[cursor];      // 它的左儿子的值
    const rightVal = list[cursor + 1]; // 它的右儿子的值
    if (leftVal != 'X') {              // 是真实节点
      const leftNode = new TreeNode(leftVal); // 创建左儿子节点
      node.left = leftNode;                   // 认父亲
      queue.push(leftNode);                   // 自己也是父亲，入列
    }
    if (rightVal != 'X') {
      const rightNode = new TreeNode(rightVal);
      node.right = rightNode;
      queue.push(rightNode);
    }
    cursor += 2; // 一次考察一对儿子，指针加2
  }
  return root;  // BFS结束，构建结束，返回根节点
};