JavaScriptで二分木を反転する方法【再帰を使った実装をわかりやすく解説】

はじめに

本記事では、JavaScriptを使って二分木（バイナリツリー）を反転（ミラーリング）する方法を解説します。木の反転とは、すべてのノードに対して左の子と右の子を入れ替える操作のことで、木全体が鏡写しのようにひっくり返るイメージです。

まず、次のような二分木があると仮定しましょう。

      4
    /    \
   2      7
  / \    / \
 1  3    6   9

この二分木を反転すると、左右が完全に入れ替わり、次のような形になります。

      4
      / \
    7    2
   / \ / \
  9  6 3  1

それでは、この反転処理をJavaScriptでどのように実装すればよいのか、具体的なコードを見ていきましょう。

反転処理の実装コード

ここでは、単一のノードを表すNodeクラスと、二分木全体を管理するBinaryTreeクラスを定義します。BinaryTreeクラスには、ノード挿入用のinsert、反転用のinvert、そして木の内容を確認するための走査メソッドtraverseを実装しています。

// 単一のツリーノードを表すクラス
class Node {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

// 二分木を表すクラス
class BinaryTree {
    constructor() {
        // 二分木のルート
        this.root = null;
    }

    // ノードを挿入するメソッド
    insert = (data) => {
        // 挿入する新しいノードを作成
        const newNode = new Node(data);
        // ルートが空なら、このノードがルートになる
        if (this.root === null) {
            this.root = newNode;
        } else {
            // そうでなければ、適切な挿入位置を探す
            this.insertData(this.root, newNode);
        }
    };

    // 挿入位置を再帰的に決める補助メソッド
    insertData = (node, newNode) => {
        if (newNode.val < node.val) {
            if (node.left === null) {
                node.left = newNode;
            } else {
                this.insertData(node.left, newNode);
            }
        } else {
            if (node.right === null) {
                node.right = newNode;
            } else {
                this.insertData(node.right, newNode);
            }
        }
    };

    // 二分木を反転するメソッド
    invert = (node) => {
        // ベースケース：ノードがnullなら何もしない
        if (node === null) {
            return;
        }
        // 分割代入で左右の子を入れ替える
        [node.left, node.right] = [node.right, node.left];
        // 左右の部分木も再帰的に反転
        this.invert(node.right);
        this.invert(node.left);
    }

    // 右→自分→左の順で走査し、値を出力するメソッド
    traverse = (node) => {
        if (node === null) {
            return;
        }
        this.traverse(node.right);
        console.log(node.val);
        this.traverse(node.left);
    };
}

// 二分木を構築
const Tree = new BinaryTree();
Tree.insert(2);
Tree.insert(7);
Tree.insert(4);
Tree.insert(1);
Tree.insert(9);
Tree.insert(3);
Tree.insert(6);

// 反転前：右から左への順で走査
Tree.traverse(Tree.root);

// 木を反転
Tree.invert(Tree.root);
console.log('after inversion');

// 反転後：同じ順序で再度走査
Tree.traverse(Tree.root);

実行結果

コンソールに出力される内容は次のとおりです。反転によって走査結果の順序が逆になっていることが確認できます。

9
7
6
4
3
2
1
after inversion
1
2
3
4
6
7
9

コードのポイント解説

invertメソッドの仕組み

反転処理の中核となるのはinvertメソッドです。ポイントは次の2点です。

• 分割代入による入れ替え：[node.left, node.right] = [node.right, node.left] を使うことで、一時変数を用意せずに左右の子をスマートに交換できます。
• 再帰的な処理：現在のノードの左右を入れ替えた後、さらにその子ノードたちに対してinvertを再帰的に呼び出すことで、木全体が反転されます。

計算量

• 時間計算量：O(n) — すべてのノードをちょうど1回ずつ訪問するためです。
• 空間計算量：O(h) — 再帰呼び出しのスタックの深さは木の高さhに依存します。木が偏っている最悪の場合はO(n)になります。

まとめ

JavaScriptで二分木を反転するには、再帰を使って各ノードの左右の子を入れ替えていくのがシンプルかつ効果的です。ES2015以降の分割代入を活用すれば、交換処理も簡潔に書けます。二分木の操作はアルゴリズムの基礎であり、面接対策にも役立つ定番テーマなので、ぜひ本記事のコードを実際に動かして理解を深めてください。