BFE.devでのAI解答例 - JavaScript コーディング問題
110. 二分木の直列化と復元

まず、二分木のノードを表すためにクラスを定義しましょう。

class Node {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

次に、与えられた配列をもとに二分木を復元するdeserialize() を実装します。二分木を配列に直列化したときに、配列のインデックスと二分木の深さが対応するため、再帰を使って深さごとに木を構築することができます。

function deserialize(arr) {
  let index = 0;
  const constructTree = (depth) => {
    if (index >= arr.length || arr[index] === null) {
      index++;
      return null;
    }
    const node = new Node(arr[index++]);
    node.left = constructTree(depth + 1);
    node.right = constructTree(depth + 1);
    return node;
  };
  return constructTree(0);
}

最後に、serialize() を実装します。ここでは、深さ優先探索を使って二分木を配列に直列化します。このとき、子ノードが存在しない場合はnullの代わりにundefinedを配列に追加します。

function serialize(root) {
  const arr = [];
  const serializeTree = (node) => {
    if (!node) {
      arr.push(null);
      return;
    }
    arr.push(node.val);
    serializeTree(node.left);
    serializeTree(node.right);
  };
  serializeTree(root);
  return JSON.stringify(arr);
}

以上の実装で、問題のテストを通過することができます。完全なコードは以下のとおりです。

class Node {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

function deserialize(arr) {
  let index = 0;
  const constructTree = (depth) => {
    if (index >= arr.length || arr[index] === null) {
      index++;
      return null;
    }
    const node = new Node(arr[index++]);
    node.left = constructTree(depth + 1);
    node.right = constructTree(depth + 1);
    return node;
  };
  return constructTree(0);
}

function serialize(root) {
  const arr = [];
  const serializeTree = (node) => {
    if (!node) {
      arr.push(null);
      return;
    }
    arr.push(node.val);
    serializeTree(node.left);
    serializeTree(node.right);
  };
  serializeTree(root);
  return JSON.stringify(arr);
}