[Google] Serialization and Deserialization BST 二叉树编码和解码

这是一道Google的面试题. 当我第一次看到这题的时候, 第一个感觉, 树, 编码,解码, 那不就是Prufer Code么. 拿起笔就开始写, 后来感觉电面不应该这么复杂, 而且Prufer code对象是Labeled Tree, 这里并没有使用到BST的特殊性质. 于是赶紧回想刷过的题, 突然想起Leetcode上面的编码方式:

366217AB-88A8-40A3-9523-8E9918836AAB这个编码的特点是:

  1. Inorder Traversal.
  2. Null = #
  3. Code容易写.

所以编码的code是:

解码的特点是:

  1. 因为已知编码是Inorder, 所以解码也是Inorder
  2. 要注意如果解码到#, 需要return null.

所以解码的code是: