3-27 297. 二叉树的序列化与反序列化

Date：2022-03-27 17:45:31

标签：

• 深度优先算法
• 序列化

题目：297. 二叉树的序列化与反序列化 ( 困难😟 )

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

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

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

示例

示例 1：

输入：root = [1,2,3,null,null,4,5]
输出：[1,2,3,null,null,4,5]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

示例 4：

输入：root = [1,2]
输出：[1,2]

分析

• 深度优先

  注意：shift 和 unshift 操作是费时的，用 pop 效率可以提高 10 倍

  O(n), O(n)

问题：

• 反转一个数组，时间复杂度为多少？

  O(n), O(1)

题解

深度优先

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

import { arr2tree, TreeNode } from './common/utils'

/*
 * Encodes a tree to a single string.
 */
function serialize(root: TreeNode | null): string {
  let res: string[] = []
  rSerialize(root)

  return res.join(',')

  function rSerialize(root: TreeNode | null) {
    if (root == null) {
      res.push('#')
      // str += 'None,'
    } else {
      // str += root.val + ','
      // str = `${str}${root.val},`
      res.push(`${root.val}`)
      rSerialize(root.left)
      rSerialize(root.right)
    }
  }
}

/*
 * Decodes your encoded data to tree.
 */
function deserialize(data: string): TreeNode | null {
  const arr = data.split(',').reverse()

  return rDeserialize(arr)

  function rDeserialize(arr: string[]) {
    // const val = arr.shift()
    // !!shift and unshift is time-consuming
    const val = arr.pop()

    if (val == '#') {
      return null
    }

    const root = new TreeNode(+val)
    root.left = rDeserialize(arr)
    root.right = rDeserialize(arr)

    return root
  }
}

使用

function main() {
  // const root = arr2tree([1, 2, 3, null, null, 4, 5])
  const root = arr2tree([1, 2, 3, null, null, 4, 5])

  console.log('[root]:', root)

  console.log('[]:', serialize(root))
  console.log('[]:', deserialize(serialize(root)))
}

main()

export {}