JavaScriptで2つの異なるツリーを比較する方法

1. 深さ優先探索（DFS）: 深さ優先探索を使用して、ツリーのノードを再帰的に比較します。次のようなコード例を使用できます。

   function compareTrees(tree1, tree2) {
    if (tree1 === null && tree2 === null) {
      return true; // ツリーが両方とも終端ノードに到達した場合は一致とみなす
    }
    if (tree1 === null || tree2 === null) {
      return false; // ツリーのいずれかが終端ノードに到達した場合は一致しない
    }
    if (tree1.value !== tree2.value) {
      return false; // 現在のノードの値が異なる場合は一致しない
    }
    return (
      compareTrees(tree1.left, tree2.left) && // 左のサブツリーを比較
      compareTrees(tree1.right, tree2.right) // 右のサブツリーを比較
    );
   }

   上記のコードでは、tree1とtree2のノードを再帰的に比較しています。両方のノードが終端ノードに到達し、かつ値が一致する場合にのみ一致と判断されます。

2. 幅優先探索（BFS）: 幅優先探索を使用して、ツリーのノードをレベルごとに比較します。次のようなコード例を使用できます。

   function compareTrees(tree1, tree2) {
    const queue1 = [tree1];
    const queue2 = [tree2];
    while (queue1.length && queue2.length) {
      const node1 = queue1.shift();
      const node2 = queue2.shift();
      if (node1.value !== node2.value) {
        return false; // 現在のノードの値が異なる場合は一致しない
      }
      if (node1.left && node2.left) {
        queue1.push(node1.left);
        queue2.push(node2.left);
      } else if (node1.left || node2.left) {
        return false; // 片方のノードだけに子が存在する場合は一致しない
      }
      if (node1.right && node2.right) {
        queue1.push(node1.right);
        queue2.push(node2.right);
      } else if (node1.right || node2.right) {
        return false; // 片方のノードだけに子が存在する場合は一致しない
      }
    }
    return queue1.length === queue2.length;
   }

   上記のコードでは、queue1とqueue2を使用してツリーのノードをレベルごとに比較しています。ノードの値が異なる場合や、片方のノードにのみ子が存在する場合は一致しないと判断されます。

これらは2つの異なるツリーを比較するための基本的なアプローチです。他にもさまざまな比較方法がありますが、ここで紹介した方法はよく使われるものです。