297. Serialize and Deserialize Binary Tree

Design an algorithm to serialize a binary tree to a string and deserialize that string back to the original tree.

Write nodes in BFS order with '#' for null children (the LeetCode format). Decode by handing out children to queued parents two tokens at a time.

1function serialize(root: TreeNode | null): string {
2  const out: string[] = [], queue = [root];
3  while (queue.length) {
4    const n = queue.shift()!;
5    out.push(n ? String(n.val) : "#");
6    if (n) queue.push(n.left, n.right);
7  }
8  return out.join(",");
9}
10function deserialize(data: string): TreeNode | null {
11  const tokens = data.split(",");
12  if (tokens[0] === "#") return null;
13  const root = new TreeNode(Number(tokens[0])), queue = [root];
14  let i = 1;
15  while (queue.length) {
16    const n = queue.shift()!;
17    const l = tokens[i++], r = tokens[i++];
18    if (l !== "#") queue.push((n.left = new TreeNode(Number(l))));
19    if (r !== "#") queue.push((n.right = new TreeNode(Number(r))));
20  }
21  return root;
22}

tree

tokens

Write 1; queue its children.

1 / 0

Space: play/pause · ←/→: step