二叉树怎样序列化和反序列化？前序加空标记和层序两种写法有什么区别？

简答

比如要把一棵二叉树存进 localStorage 或者通过接口发给别人，就得先把它变成字符串，这叫序列化；拿到字符串再把原来的树建回来，叫反序列化。LeetCode 297 就是这道题，它不限定格式，只要求能还原成原来的结构。

难点在空节点。只记录节点值的话，同一串值可以对应好几棵形状不同的树，所以空的位置也要记下来。前序写法遇到空节点写一个 #，层序写法写 null，有了这些标记，结构就唯一确定了。

两种写法各有用处。前序写法代码短，序列化和反序列化都是同一个递归顺序，读一个标记建一个节点；层序写法和 LeetCode 题面的 [1,2,3,null,null,4,5] 格式一样，用队列一层层处理，树很深时也不会递归太深。

要注意两点。第一，反序列化必须严格按序列化时的顺序读，前序就前序、层序就层序。第二，层序写法末尾的 null 可以省掉，但还原时要处理右孩子标记读不到的情况。

为什么空节点必须记下来

只记录前序遍历的值，1,2 既可以是“2 是 1 的左孩子”，也可以是“2 是 1 的右孩子”，两棵树的前序结果一样，所以无法唯一还原。前序遍历的写法见《二叉树的前序、中序、后序遍历怎样用递归和迭代写？》。

把空节点也写出来就不一样了。左孩子的情况写成 1,2,#,#,#，右孩子的情况写成 1,#,2,#,#。每个节点后面紧跟着它的左子树和右子树，空子树也占一个位置，读的时候每一步该建哪个节点就确定了。

前序加空标记的写法

下面用 LeetCode 题面示例里的树：根是 1，左孩子 2，右孩子 3，3 下面挂着 4 和 5。

JavaScript

function TreeNode(val, left = null, right = null) {
  this.val = val;
  this.left = left;
  this.right = right;
}

function serialize(root) {
  const out = [];
  function walk(node) {
    if (node === null) {
      out.push('#');
      return;
    }
    out.push(String(node.val));
    walk(node.left);
    walk(node.right);
  }
  walk(root);
  return out.join(',');
}

function deserialize(data) {
  const tokens = data.split(',');
  let i = 0;
  function build() {
    const token = tokens[i++];
    if (token === '#') return null;
    const node = new TreeNode(Number(token));
    node.left = build();
    node.right = build();
    return node;
  }
  return build();
}

const root = new TreeNode(1, new TreeNode(2), new TreeNode(3, new TreeNode(4), new TreeNode(5)));
const text = serialize(root);
console.log(text); // 1,2,#,#,3,4,#,#,5,#,#
console.log(serialize(deserialize(text)) === text ? '一致' : '不一致'); // 一致
console.log(serialize(null)); // #
console.log(deserialize('#') === null ? '空树' : '非空'); // 空树

序列化结果是 1,2,#,#,3,4,#,#,5,#,#。2 是叶子，所以后面跟着两个 #，分别代表它的空左孩子和空右孩子。

为什么反序列化只用一个下标 i 就够了？因为 build 的顺序和 walk 完全一样：先读当前节点，再递归建左子树，再递归建右子树。左子树建完时，i 正好停在右子树的第一个标记上。读到 # 就返回 null，递归自然在这里停下。

空树序列化成 #，还原回来是 null，不需要额外判断。这种写法的缺点是递归深度等于树高，题目约束节点数最多 10⁴，如果树退化成一条链，递归就有一万层，可以按需改成用栈的迭代写法。

层序写法

层序写法就是 LeetCode 题面用的格式。序列化时用队列按层取节点，空孩子也放进队列，取到空的写 null；层序遍历本身见《二叉树怎样层序遍历、求最大深度？》。

JavaScript

function TreeNode(val, left = null, right = null) {
  this.val = val;
  this.left = left;
  this.right = right;
}

function serialize(root) {
  if (root === null) return '';
  const out = [];
  const queue = [root];
  let head = 0;
  while (head < queue.length) {
    const node = queue[head++];
    if (node === null) {
      out.push('null');
      continue;
    }
    out.push(String(node.val));
    queue.push(node.left, node.right);
  }
  // 末尾的 null 不影响还原，去掉后和 LeetCode 的写法一致。
  while (out[out.length - 1] === 'null') out.pop();
  return out.join(',');
}

function deserialize(data) {
  if (data === '') return null;
  const tokens = data.split(',');
  const root = new TreeNode(Number(tokens[0]));
  const queue = [root];
  let head = 0;
  let i = 1;
  while (i < tokens.length) {
    const parent = queue[head++];
    const leftToken = tokens[i++];
    if (leftToken !== 'null') {
      parent.left = new TreeNode(Number(leftToken));
      queue.push(parent.left);
    }
    const rightToken = tokens[i++];
    if (rightToken !== undefined && rightToken !== 'null') {
      parent.right = new TreeNode(Number(rightToken));
      queue.push(parent.right);
    }
  }
  return root;
}

const root = new TreeNode(1, new TreeNode(2), new TreeNode(3, new TreeNode(4), new TreeNode(5)));
const text = serialize(root);
console.log(text); // 1,2,3,null,null,4,5
console.log(serialize(deserialize(text)) === text ? '一致' : '不一致'); // 一致
console.log(deserialize('1,2,3,null,null,4,5').right.left.val); // 4
console.log(serialize(null) === '' ? '空字符串' : '非空'); // 空字符串

结果是 1,2,3,null,null,4,5，和题面示例的输入一样。2 的两个孩子是空的，写成两个 null；4 和 5 的孩子也是空的，但都在末尾，被去掉了。

反序列化为什么能把值挂到正确的父节点上？因为字符串里非空节点出现的顺序，就是它们进队列的顺序。队列里每取出一个父节点，就从字符串里往后读两个标记，分别作为它的左孩子和右孩子，非空的孩子再进队列，等着之后挂它们自己的孩子。

末尾的 null 被去掉了，所以最后一个父节点的右孩子标记可能读不到，tokens[i++] 会得到 undefined，代码里要把它当成空孩子。题面示例 2 的空树，这里序列化成空字符串，反序列化时先判断空字符串直接返回 null。

这两种写法时间复杂度都是 O(n)，每个节点和空标记各处理一次。层序写法用循环加队列，不会因为树深导致递归过深；前序写法代码更短，面试时手写更不容易出错。

常见追问

只用前序和中序遍历结果能还原二叉树吗？

节点值互不相同时可以。前序的第一个是根，在中序里找到根，左边是左子树、右边是右子树，再递归处理。但 297 题没有说节点值不重复，值在 -1000 到 1000 之间，节点却可以有 10⁴ 个，必然有重复，所以这道题要用带空标记的写法。

为什么队列用下标 head 往后走，而不是 shift？

shift 每次要把后面的元素往前挪，数组很长时会变慢。用一个 head 下标记录读到哪里，取元素是 O(1)，整体就是 O(n)。

节点值本身含有逗号或者 # 怎么办？

这道题的节点值都是整数，不会冲突。如果值是任意字符串，就要对值做转义，或者改成先写长度再写内容的格式，也可以直接用 JSON.stringify 处理值，保证分隔符不会和值混在一起。