题目

题目来源：力扣（LeetCode）

序列化是将数据结构或对象转换为一系列位的过程，以便它可以存储在文件或内存缓冲区中，或通过网络连接链路传输，以便稍后在同一个或另一个计算机环境中重建。

设计一个算法来序列化和反序列化 二叉搜索树 。 对序列化/反序列化算法的工作方式没有限制。 您只需确保二叉搜索树可以序列化为字符串，并且可以将该字符串反序列化为最初的二叉搜索树。

编码的字符串应尽可能紧凑。

示例 1：

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

示例 2：

输入：root = []
输出：[]

思路分析

  1. 二叉树结构是一个二维平面内的结构，而序列化出来的字符串是一个线性的一维结构。所谓的序列化就是把结构化的数据 “打平”。

  2. 对于二叉树来说需要中序遍历结果与前序或后序结果结合才能构建出来，而二叉搜索树根据特性（右子树 > 根 > 左子树）只需要前序或后序遍历结果就可以构建出来。

  3. 在序列化时，利用前序遍历将节点值存在一个数组中，然后通过空格分割节点值，将数组转换成字符串，从而完成序列化操作

  4. 根据二叉搜索树的性值：中序遍历的结果是从小到大有序的，所以可以根据前序遍历的结果，获取到前序遍历的数组，然后对数组进行升序排序后，就得到了中序遍历的结果数组，这样利用前序和中序遍历的结果数组，就可以和 105.从前序与中序遍历序列构造二叉树 一样的方式构建一颗二叉树。

  1. /**
  2. * Definition for a binary tree node.
  3. * function TreeNode(val) {
  4. * this.val = val;
  5. * this.left = this.right = null;
  6. * }
  7. */
  8. /**
  9. * Encodes a tree to a single string.
  10. *
  11. * @param {TreeNode} root
  12. * @return {string}
  13. */
  14. // 利用前序遍历将节点存在一个数组中，然后通过空格分割节点，将数组转换成字符串，从而完成序列化操作
  15. var serialize = function (root) {
  16.   if (root === null) {
  17.     return '';
  18.   }
  19.   let stringArray = [];
  20.   var postDFS = function (node) {
  21.     if (node === null) {
  22.       return;
  23.     }
  24.     // 前序遍历二叉树
  25.     stringArray.push(node.val)
  26.     postDFS(node.left);
  27.     postDFS(node.right);
  28.   }
  29.   postDFS(root)
  30.   // 以空格分割节点，转换成字符串
  31.   return stringArray.join(' ');
  32. };
  33. /**
  34. * Decodes your encoded data to tree.
  35. *
  36. * @param {string} data
  37. * @return {TreeNode}
  38. */
  39. var deserialize = function (data) {
  40.   if (data.length === 0) {
  41.     return null;
  42.   }
  43.   // 将序列化的节点转换成数组，该数组为前序遍历的结果
  44.   let preorder = data.split(' ').map(item => {
  45.     return Number.parseInt(item);
  46.   })
  48.   // 根据前序遍历的结果转换成中序遍历的结果
  49.   let inorder = [...preorder];
  50.   inorder.sort((a, b) => {
  51.     return a - b;
  52.   })
  54.   // 获取二叉树长度
  55.   let preLen = preorder.length;
  56.   let inLen = inorder.length;
  57.   // 优化操作，建立一个 map 存储中序遍历 inorder 值对应的下标，用于根据值快速找到inorder的下标
  58.   let map = new Map();
  59.   for (let i = 0; i < inLen; i++) {
  60.     map.set(inorder[i], i);
  61.   }
  63.   // 根据前序遍历和中序遍历的结果数组构建二叉树
  64.   const build = function (preorder, preLeft, preRight, map, inLeft, inRight) {
  65.     // 中止条件，区间不存在值,返回空节点
  66.     if (preLeft > preRight || inLeft > inRight) {
  67.       return null;
  68.     }
  70.     // 构造根节点  前序遍历的结果数组的第一个元素是根节点
  71.     let root = new TreeNode(preorder[preLeft]);
  72.     // 获取中序遍历下标，这样就能根据中序遍历的规则，知道左右子树区间长度
  73.     let pIndex = map.get(root.val);
  74.     // 构建左节点，传入构建完根节点后的左子树下标区间
  75.     root.left = build(preorder, preLeft + 1, pIndex - inLeft + preLeft, map, inLeft, pIndex - 1);
  76.     // 构建右节点，传入构建完根节点后的右子树下标区间
  77.     root.right = build(preorder, pIndex - inLeft + preLeft + 1, preRight, map, pIndex + 1, inRight);
  78.     return root;
  79.   }
  80.   // 返回递归函数，传入默认值,参数值为前序遍历与中序遍历的下标区间
  81.   return build(preorder, 0, preLen - 1, map, 0, inLen - 1);
  82. };
  83.   /**
  84. * Your functions will be called as such:
  85. * deserialize(serialize(root));
  86. */