问题描述

序列化是将数据或者对象转换为二进制的过程，因此可以被存储在文件或者内存中，或是通过网络进行传输，在同一台或者另一台电脑上可被重新恢复为原来的数据。

设计一个算法来序列化和反序列化二叉搜索树。对于算法没有任何限制。只需要保证将二叉搜索树序列化为字符串，并且该字符串可被反序列化成原先的树结构。

序列化后的字符串应该尽量紧凑。

注意：不要使用类中的成员/全局/静态变量来存储状态。序列化和反序列化应该是无状态的。

想看英文原文的戳这里。

解题思路

解此题的关键是利用二叉搜索树的相关性质，即：

左子树的值 < 父节点的值。
右子树的值 > 父节点的值。

若要重建二叉搜索树，只需将节点一个个的按照规则进行插入即可。但是节点的插入顺序是影响重建的重要因素。因此，在序列化时，遍历的顺序比较重要。

其中满足条件的遍历方式有两种：

先序遍历
层遍历

至于为什么是这两种，可使用各种遍历方式自行分析一下，比较简单。

所以解题步骤如下：

采用先序/层遍历方式，将节点值存储下来。
构建二叉搜索树。根据这些节点值，不断的将其插入到二叉搜索树中。

下面给出先序遍历的解法，以 - 连接节点。

var serialize = function (root) {
  if (root) {
    return `-${root.val}` + serialize(root.left) + serialize(root.right)
  }

  return ''
};

反序列化：

var deserialize = function (data) {
  let str = data
  if (str && str.length > 0) {
    // 去除首个 -，因为 split 后是空格
    if (str.startsWith('-')) {
      str = str.substring(1, str.length)
    }

    let array = str.split('-')

    if (array.length >= 1) {

      let root = null
      let i = 0
      while (i < array.length) {
        // 将节点逐个插入
        root = buildTree(root, parseInt(array[i]))
        i += 1
      }

      return root
    }
  }

  return null
};

// 构建树
var buildTree = function (root, val) {
  if (!root) {
    return new TreeNode(val)
  }

  if (val < root.val) {
    root.left = buildTree(root.left, val)
  } else {
    root.right = buildTree(root.right, val)
  }

  return root
}

完整代码可点此查看。