序列化与反序列化

为什么序列化必须显式编码空节点？

• 目的: 把树转成字符串以便存储或传输, 另一端还原成等价的树;
• 关键: 只用节点值无法确定结构, 必须给空节点留一个不会与节点值冲突的标记;

前序序列化如何编码？

• 规则: 前序遍历输出节点值, 空节点输出占位标记, 用分隔符连接;

const serialize = function (root) {
  const dfs = (node) => {
    if (node == null) return "#";
    return node.val + "," + dfs(node.left) + "," + dfs(node.right);
  };

  return dfs(root);
};

反序列化如何还原？

• 做法: 按分隔符切开, 依次消费 token; 遇到空标记返回 null, 否则先建根节点再递归建左右子树;
• 依据: token 的消费顺序与序列化时的前序顺序一致;

const deserialize = function (data) {
  const tokens = data.split(",");
  const dfs = () => {
    const value = tokens.shift();
    if (value === "#") return null;
    const node = new TreeNode(Number(value));
    node.left = dfs();
    node.right = dfs();
    return node;
  };

  return dfs();
};

复杂度如何？

• 时间: O(n), 每个节点只处理一次;
• 空间: O(n), 递归栈与 token 数组;
• 其它口径: 层序序列化同样可行, 也必须编码空节点, 见 层序遍历;