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

JSON 的运用非常广泛，比如我们经常将语言中的结构体序列化成 JSON 字符串，存入缓存或者通过网络发送给远端，接收方接收到 JSON 字符串之后进行反序列化就可以得到原始数据了。这就是「序列化」与「反序列化」的目的，以某种固定格式组织字符串，使得数据可以独立与编程语言。

假设现在有一棵用 Java 实现的二叉树，我想把它序列化成字符串，然后用 C++ 读取并还原这棵二叉树结构，怎么办？这就需要对二叉树进行「序列化」和「反序列化」了。

本文会用前序、中序、后序遍历的方式来序列化和反序列化二叉树，进一步还会用迭代式的层级遍历来解决这个问题。

题目描述

「二叉树的序列化与反序列化」就是给你输入一棵二叉树的根节点 root，要求你实现一个这样的类：

class Codec {
  // 把一棵二叉树序列化成字符串
  public serialize(root: TreeNode): string {}
  
  // 把字符串反序列化成二叉树
  public deserialize(data: string): TreeNode {}
}

不限制序列化的格式，只需要这两种方法能够自洽即可。

想象一下，二叉树应该是一个二维平面的结构，而序列化出来的字符串是一个线性的一位结构。所谓的序列化不过就是把结构化的数据「打平」，其实就是在考察二叉树的遍历方式。

二叉树的遍历方式有哪些？递归遍历方式有前序遍历、中序遍历、后序遍历；迭代方式一般是层级遍历。

本文就把这些方式都尝试一遍，来实现序列化与反序列化。

前序遍历

前序遍历的框架讲过很多次了，这里就不再重复。这里我们想象一下当进行前序遍历时，res 输出列表大概是怎样的。

那么 res = [1, 2, #, 4, #, #, 3, #, #] 就是将二叉树「打平」到了一个列表中，其中 # 代表 null。

因此我们可以尝试写出算法：

function serialize(root: TreeNode | null): string {
  const res: string[] = []
  
	function traverse(root: TreeNode | null): void {
    if(!root) {
      res.push('#')
      return
    }
    
    res.push(root.val)
    traverse(root.left)
    traverse(root.right)
  }
  
  traverse(root)
  
  return res.join(',')
}

至此，我们完成了 serialize 方法，现在我们开始写 deserialize 方法，将字符串反过来构造二叉树。

一般情况下，单单前序遍历结果是不能还原二叉树结构的，因为缺少控制真的信息，至少要得到前序、中序、后序遍历中的两种才能还原二叉树，但是现在我们在设计序列化函数的时候就已经包含空指针信息了，所以可以进行还原。

我们已经知道了前序遍历的顺序，将字符串转换成列表后，就可以得到根节点，所以按照前序遍历规则，递归生成左右子树即可。

function deserialize(data: string): TreeNode | null {  
  const list = data.split(',')
 
  function traverse(nodes: string[]): TreeNode | null {
    if(!nodes.length) return null
    
    const first = nodes.shift()
    if(first === '#') return null
    
    const root = new TreeNode(+first)
    root.left = traverse(nodes)
    root.right = traverse(nodes)
    
    return root
  }
  
  return traverse(list)
}

我们发现书的递归性质，nodes 列表的第一个元素就是一棵树的根节点，所以只要将列表的第一个元素取出来作为根节点，剩下的交给递归函数去解决即可。

后序遍历

明白了前序遍历，后序遍历实现起来就非常简单，只需要简单调整一下函数插入数组的顺序即可：

function serialize(root: TreeNode | null): string {
  const res: string[] = []
  
	function traverse(root: TreeNode | null): void {
    if(!root) {
      res.push('#')
      return
    }
    
    traverse(root.left)
    traverse(root.right)
    res.push(root.val)
  }
  
  traverse(root)
  
  return res.join(',')
}

难点在于如何实现 deserialize 函数，也就是如何确定根节点。

依照后序遍历的规则，生成的字符串的最后一位应该是二叉树的根节点，然后依次构造出 右子树 ，然后才是 左子树 ：

function deserialize(data: string): TreeNode | null {
  const list = data.split(',')
  
  function traverse(nodes: string[]): TreeNode | null {
		if(!nodes.length) return null
    
    const cur = nodes.pop()
    if(cur === '#') return null
    
    const root = new TreeNode(cur)
    root.right = traverse(nodes)
    root.left = traverse(nodes)
    
    return root
  }
  
  return traverse(list)
}

中序遍历

先说结论： 中序遍历方法无法做到反序列化，因为无法确定根节点的位置。

前序遍历根节点在列表首位，后序遍历根节点在列表末尾，都可以精确知道根节点的位置。

中序遍历因为根节点夹在左右子树中间，所以无法知道根节点的具体位置，所以无法实现反序列化。