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

Tips

题目类型: Tree

题目

序列化和反序列化一棵树, 怎么设计序列化的结构都行, 最后能保证 deserialize(serialize(root)) 成功执行, 自圆其说就行.

题解

序列化用个递归的前序遍历就 ok, 反序列化用个递归也 ok.

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

const SEP = ','
const NULL = '#'

/**
 * Encodes a tree to a single string.
 *
 * @param {TreeNode} root
 * @return {string}
 */
var serialize = function (root) {
  const arr = []
  serializeBuilder(root, arr)
  return arr.join('')
}

var serializeBuilder = function (root, arr) {
  if (!root) {
    arr.push(`${NULL}${SEP}`)
  } else {
    arr.push(`${root.val}${SEP}`)
    serializeBuilder(root.left, arr)
    serializeBuilder(root.right, arr)
  }

  return arr
}

/**
 * Decodes your encoded data to tree.
 *
 * @param {string} data
 * @return {TreeNode}
 */
var deserialize = function (data) {
  const arr = data.split(SEP)
  return deserializeBuilder(arr)
}

var deserializeBuilder = function (arr) {
  if (arr.length === 0) return null
  const nodeVal = arr.shift()
  if (nodeVal === NULL) return null

  const root = new TreeNode(+nodeVal)
  root.left = deserializeBuilder(arr)
  root.right = deserializeBuilder(arr)

  return root
}

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

参考

二叉树的题, 就那几个框架, 枯燥至极 🤔 这篇文章讲了各种序列化/反序列化的方式.