二叉树的序列化与反序列化 ​

const serialize = root => {
  if (!root) return '#'
  const valL = serialize(root.left)
  const valR = serialize(root.right)
  return root.val + ',' + valL + ',' + valR
}
const deserialize = str => {
  const nodes = str.split(',')
  const build = nodes => {
    const rootVal = nodes.shift()  // 前序遍历，第一项是根节点
    if (rootVal === '#') return null
    const root = new TreeNode(rootVal)
    root.left = build(nodes)  // 先构造左子树
    root.right = build(nodes)  // 再构造右子树
    return root
  }
  return build(nodes)
}

const serialize = root => {
  if (!root) return '#'
  const valL = serialize(root.left)
  const valR = serialize(root.right)
  return valL + ',' + valR + ',' + root.val
}
const deserialize = str => {
  const nodes = str.split(',')
  const build = nodes => {
    const rootVal = nodes.pop()  // 后序遍历，最后一项是根节点
    if (rootVal === '#') return null
    // ==> 入栈顺序：根 => 右 => 左
    const root = new TreeNode(rootVal)
    root.right = build(nodes)
    root.left = build(nodes)
    // <==
    return root
  }
  return build(nodes)
}

const serialize = (root, ret = []) => {
  const queue = [root]
  while (queue.length) {
    const node = queue.shift()
    if (node) {
      ret.push(node.val) // 出队时保存节点值
      queue.push(node.left)
      queue.push(node.right)
    } else {
      ret.push('#')
    }
  }
  return ret.join(',')
}
const deserialize = str => {
  if (str === '#') return null
  const nodes = str.split(',')
  const root = new TreeNode(nodes.shift())
  const queue = [root]
  while (nodes.length) {
    const node = queue.shift()
    const [valL, valR] = [nodes.shift(), nodes.shift()]
    if (valL !== '#') {  // 是真实节点
      const nodeL = new TreeNode(valL)  // 创建左子节点
      node.left = nodeL  // 连接
      queue.push(nodeL)  // 入队
    }
    if (valR !== '#') {
      const nodeR = new TreeNode(valR)
      node.right = nodeR
      queue.push(nodeR)
    }
  }
  return root
}