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);}