C++で二分木の葉ノードをペアごとに入れ替える方法

二分木が与えられたとき、その葉ノードをペアごとに入れ替えることが課題です。例えば、次のような入出力が考えられます。

入力：

出力：

本記事では、隣接する2つの葉ノードを指す2つのポインタを管理しながら、それらの値を順番に入れ替えていく方法を解説します。

解法のアプローチ

このアプローチでは、木を走査して葉ノードを見つけると同時に、カウンタで現在の葉ノードの個数を追跡します。ポイントとなるのは次のロジックです。

• カウンタが奇数のとき：まだペアの片方しか見つかっていないため、1つ目のポインタをそのノードに向ける。
• カウンタが偶数のとき：ペアが揃ったことになるので、2つのノードのデータを入れ替える。

この仕組みにより、隣接する葉ノード同士を順番にスワップすることができます。

C++による実装例

上記のアプローチを実装したC++コードは以下の通りです。

#include <bits/stdc++.h>
using namespace std;
struct Node{ // 木のノード構造体
    int data;
    struct Node *left, *right;
};
void Swap(Node **a, Node **b){ // 値を入れ替えるユーティリティ関数
    Node * temp = *a;
    *a = *b;
    *b = temp;
}
/******** 葉ノードを入れ替えるためのポインタ ********/
Node **firstleaf;
Node **secondleaf;
void SwapTheLeafNodes(Node **root, int &count){// 葉ノードを
// 入れ替えるための再帰関数
    if (!(*root)) // rootがNULLなら何もせず戻る
        return;
    if(!(*root)->left &&!(*root)->right){ // 葉ノードの条件
        secondleaf = root; // まず2つ目のポインタをこのノードに向ける
        count++; // カウントを増やす
        if (count%2 == 0) // カウントが偶数ならペアが揃ったので入れ替える
            Swap(firstleaf, secondleaf);
        else // カウントが奇数ならまだ1つ目のノードしか見つかっていない
            firstleaf = secondleaf;
    }
    if ((*root)->left)
        SwapTheLeafNodes(&(*root)->left, count);
    if ((*root)->right)
        SwapTheLeafNodes(&(*root)->right, count);
}
Node* newNode(int data){ // 新しいノードを初期化する関数
    Node *temp = new Node;
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}
void printInorder(Node* node){ // 中間順走査の関数
    if (node == NULL)
       return;
    printInorder(node->left);
    printf("%d ", node->data);
    printInorder(node->right);
}
int main(){
   /* 二分木の作成 */
    Node *root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->right->left = newNode(5);
    root->right->right = newNode(8);
    root->right->left->left = newNode(6);
    root->right->left->right = newNode(7);
    root->right->right->left = newNode(9);
    root->right->right->right = newNode(10);
    cout << "Inorder traversal before swap:\n";
    printInorder(root);
    cout << "\n";
    int count = 0; // 葉ノードを追跡するカウンタ
    SwapTheLeafNodes(&root, count); // ノードの入れ替え
    cout << "Inorder traversal after swap:\n";
    printInorder(root);
    cout << "\n";
    return 0;
}

実行結果

Inorder traversal before swap:
4 2 1 6 5 7 3 9 8 10
Inorder traversal after swap:
6 2 1 4 5 9 3 7 8 10

コードの解説

上記のコードでは、葉ノードを追跡するための2つのポインタ（firstleaf と secondleaf）を用意しています。木を再帰的に走査し、葉ノードに到達したら、まず2つ目のポインタをそのノードに向けます。続いてカウント変数をインクリメントし、カウントが偶数であれば2つのノードを入れ替え、奇数であればペアの最初の要素が見つかった段階として、そのノードを1つ目のポインタに保存します。これがこの関数の動作原理です。

なお、このアルゴリズムは木の全ノードを一度ずつ訪問するため、時間計算量は O(N)（Nはノード数）です。補助的に使うのはポインタ2つだけなので、再帰スタックを除けば空間計算量も O(1) と非常に効率的です。

まとめ

このチュートリアルでは、二分木の葉ノードをペアごとに入れ替える問題を解決しました。再帰的な走査とカウンタの偶奇判定を組み合わせることで、シンプルかつ効率的に実装できることを確認しました。同じロジックは、C、Java、Pythonなど他の言語でも同様に記述できます。本チュートリアルが皆さんの学習の一助になれば幸いです。