449. 序列化和反序列化二叉搜索树

449. 序列化和反序列化二叉搜索树

leetcode 链接

解法一：前序遍历二叉树

1、前序遍历二叉搜索树，生成数组 list；

2、那么第一个值就是根节点的值；

3、找到后面第一个比这个值大的元素的位置（rightStartIndex），[rightStartIndex, list.length - 1] 中的元素构建右子树（rightStartIndex作为右子树的根节点的值）；

4、[1, rightStartIndex] 区间的元素构建左子树（不包含rightStartIndex）；

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

/**
 * Encodes a tree to a single string.
 *
 * @param {TreeNode} root
 * @return {string}
 */
function serialize(root) {
  let res = ''
  if (root) {
    res += root.val
    if (root.left) {
      res = `${res},${serialize(root.left)}`
    }
    if (root.right) {
      res = `${res},${serialize(root.right)}`
    }
  }
  return res
}

/**
 * Decodes your encoded data to tree.
 *
 * @param {string} data
 * @return {TreeNode}
 */
function deserialize(data) {
  if (!data)
    return null
  const list = data.split(',')
  const val = Number(list[0])
  const root = new TreeNode(val)
  const rightStartIndex = list.findIndex(item => Number(item) > val)
  if (rightStartIndex > -1) {
    root.left = deserialize(list.slice(1, rightStartIndex).join(','))
    root.right = deserialize(list.slice(rightStartIndex).join(','))
  }
  else {
    root.left = deserialize(list.slice(1).join(','))
  }
  return root
}

/**
 * Your functions will be called as such:
 * deserialize(serialize(root));
 */

解法二：后续遍历二叉搜索树

官方题解

function serialize(root) {
  const list = []

  const postOrder = (root, list) => {
    if (!root) {
      return
    }
    postOrder(root.left, list)
    postOrder(root.right, list)
    list.push(root.val)
  }

  postOrder(root, list)
  const str = list.join(',')
  return str
}

function deserialize(data) {
  if (data.length === 0) {
    return null
  }
  const arr = data.split(',')
  const length = arr.length
  const stack = []
  for (let i = 0; i < length; i++) {
    stack.push(Number.parseInt(arr[i]))
  }

  const construct = (lower, upper, stack) => {
    if (
      stack.length === 0
      || stack[stack.length - 1] < lower
      || stack[stack.length - 1] > upper
    ) {
      return null
    }
    const val = stack.pop()
    const root = new TreeNode(val)
    root.right = construct(val, upper, stack)
    root.left = construct(lower, val, stack)
    return root
  }

  return construct(-Number.MAX_SAFE_INTEGER, Number.MAX_SAFE_INTEGER, stack)
}