【C++】キューを使って二分探索木（BST）のパスを反転する方法

問題の概要

二分探索木（BST）が与えられ、特定のキーからルートに至るパス上のノードの値を反転することが求められます。

たとえば次のようなイメージです。

解決のためのアプローチ

このアプローチでは、まず空のキューを用意してルートから探索を開始します。木を辿りながら経路上のノードの値を順番にキューへプッシュしていき、目的のキーを持つノードが見つかったら、再帰の帰り道でキューの先頭から順に値を書き戻します。こうすることで、パス上のノードの値がきれいに反転されます。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
struct node {
    int key;
    struct node *left, *right;
};
struct node* newNode(int item){
    struct node* temp = new node;
    temp->key = item;
    temp->left = temp->right = NULL;
    return temp;
}
void inorder(struct node* root){
    if (root != NULL) {
        inorder(root->left);
        cout << root->key << " ";
        inorder(root->right);
    }
}
void Reversing(struct node** node,
               int& key, queue<int>& q1){
    /* 木が空の場合は何もせずに返る */
    if (*node == NULL)
        return;
    if ((*node)->key == key){ // キーが見つかった場合
        q1.push((*node)->key); // その値をキューにプッシュする
        (*node)->key = q1.front(); // 現在のノードの値をキューの先頭要素で置き換える
        q1.pop(); // 先頭要素をポップする
    }
    else if (key < (*node)->key){ // キーが現在のノードの値より小さい場合
        q1.push((*node)->key); // ノードの値をキューにプッシュする
        Reversing(&(*node)->left, key, q1); // 再帰呼び出しで左部分木へ進む
        (*node)->key = q1.front(); // 値を反転させる
        q1.pop(); // 先頭要素をポップする
    }
    else if (key > (*node)->key){ // キーが現在のノードの値より大きい場合
        q1.push((*node)->key); // ノードの値をキューにプッシュする
        Reversing(&(*node)->right, key, q1); // 再帰呼び出しで右部分木へ進む
        (*node)->key = q1.front(); // ノードの値をキューの先頭要素で置き換える
        q1.pop(); // 先頭要素をポップする
    }
    return;
}
struct node* insert_node(struct node* node, // BSTにノードを挿入する関数
                          int key){
    if (node == NULL)
        return newNode(key); // 木が空の場合は新しいノードを返す
    if (key < node->key) // そうでなければ木の中に挿入する
        node->left = insert_node(node->left, key);
    else if (key > node->key)
        node->right = insert_node(node->right, key);
    return node; // ノードを返す
}
int main(){
    struct node* root = NULL;
    queue<int> q1;
    int k = 80;
/****************BSTの構築*****************/
    root = insert_node(root, 50);
    insert_node(root, 30);
    insert_node(root, 20);
    insert_node(root, 40);
    insert_node(root, 70);
    insert_node(root, 60);
    insert_node(root, 80);
    cout << "Before Reversing :" << "\n";
    inorder(root);
    cout << "\n";
    Reversing(&root, k, q1);
    cout << "After Reversing :" << "\n";
    // 反転後の木を中間順巡回で出力
    inorder(root);
    return 0;
}

実行結果

Before Reversing :
20 30 40 50 60 70 80
After Reversing :
20 30 40 80 60 70 50

コードの解説

このアプローチでは、与えられたキーを通常の二分探索と同じ要領で探していきます。探索で通過するノードの値をすべてキューに蓄えておき、キーに一致するノードが見つかった時点で、再帰呼び出しが戻っていく順序（葉側から根側へ）に合わせて、キューの先頭から値を順に書き戻します。降順にプッシュした値が昇順に取り出されて割り当てられるため、結果としてパス上の値が完全に反転します。

計算量

時間計算量は木の高さを h とすると O(h)、キューと再帰スタックを使用するため空間計算量も O(h) となります。バランスの取れたBSTであれば O(log n) に収まります。

まとめ

今回は、キューと再帰を組み合わせて、二分探索木（BST）内の指定されたキーからルートまでのパスを反転する問題を解きました。C++による実装例とともに、解法全体の流れも紹介しました。同じロジックはC、Java、Pythonなど他の言語でも同様に実装できます。本チュートリアルが皆さんの学習のお役に立てば幸いです。