Lstmxx的空间

297. 二叉树的序列化与反序列化

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

提示: 输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。

链接

前序遍历法

function serialize(root: TreeNode | null): string {
  if (root === null) return ''
  let preorder = []
  traverse(root, preorder)
  return preorder.join(',')
};

function traverse(root: TreeNode, preorder: string[]): void {
  if (root === null) {
    preorder.push('#')
    return
  }
  preorder.push(`${root.val}`)
  traverse(root.left, preorder)
  traverse(root.right, preorder)
}
/*
 * Decodes your encoded data to tree.
 */
function deserialize(data: string): TreeNode | null {
  if (data === '') return null
  const preorder = data.split(',')
  return build(preorder)
};

function build(preorder: string[]) : TreeNode | null {
  if (preorder.length === 0) {
    return null
  }
  const rootVal = preorder.shift()
  if (rootVal === '#') return null
  const root = new TreeNode(Number(rootVal))
  root.left = build(preorder)
  root.right = build(preorder)
  return root
}

后序遍历法

function serialize(root: TreeNode): string {
  const serializeList = []
  sTraverse(root, serializeList)
  return serializeList.join(',')
}

function sTraverse(root: TreeNode, serializeList: string[]): void {
  if (root === null) {
    serializeList.push('#')
    return
  }
  sTraverse(root.left, serializeList)
  sTraverse(root.right, serializeList)
  serializeList.push(`${root.val}`)
}

function deserialize(data: string): TreeNode | null {
  const serializeList = data.split(',')
  return dTraverse(serializeList)
}

function dTraverse(serializeList: string[]): TreeNode | null {
  if (serializeList.length === 0) return null
  const val = serializeList.pop()
  if (val === '#') return null
  const root = new TreeNode(Number(val))
  root.right = dTraverse(serializeList)
  root.left = dTraverse(serializeList)
  return root
}

层级遍历法

function serialize(root: TreeNode): string {
  if (root === null) return ''
  const nodeStrList: string[] = []
  const nodeQueList: TreeNode[] = []
  nodeQueList.push(root)
  while(nodeQueList.length > 0) {
    const cur = nodeQueList.shift()
    if (cur === null) {
      nodeStrList.push('#')
      continue
    }
    nodeStrList.push(`${cur.val}`)
    nodeQueList.push(cur.left)
    nodeQueList.push(cur.right)
  }
  return nodeStrList.join(',')
}


function deserialize(data: string): TreeNode | null {
  if (data === '') return null
  const nodeStrList = data.split(',')
  const root = new TreeNode(Number(nodeStrList[0]))
  const nodeQueList: TreeNode[] = [root]
  for(let i = 1, len = nodeStrList.length; i < len;) {
    const parent = nodeQueList.shift()
    const left = nodeStrList[i++]
    if (left !== '#') {
      parent.left = new TreeNode(Number(left))
      nodeQueList.push(parent.left)
    } else {
      parent.left = null
    }
    const right = nodeStrList[i++]
    if (right !== '#') {
      parent.right = new TreeNode(Number(right))
      nodeQueList.push(parent.right)
    } else {
      parent.right = null
    }
  }
  return root
}