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}
 */
var serialize = function (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}
 */
var deserialize = function (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));
 */

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

官方题解

var serialize = function (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;
};

var deserialize = function (data) {
  if (data.length === 0) {
    return null;
  }
  let arr = data.split(",");
  const length = arr.length;
  const stack = [];
  for (let i = 0; i < length; i++) {
    stack.push(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);
};