C++で二分木の最短ルートから葉までのパスを出力するプログラム

このチュートリアルでは、二分木（バイナリツリー）において、根（ルート）から葉（リーフ）までの最短パスのうち最初に見つかったものを出力するC++プログラムについて解説します。

ここでは、すべてのノードが異なる値を持つ二分木が与えられ、その木の中で根ノードから葉ノードまでの最短経路を見つける必要があります。

この問題を解くには、キュー（queue）を使って二分木をレベル順走査（幅優先探索）し、最短パス上のノードを記録する方法が有効です。具体的には、最も浅いレベルにある最初の葉ノードに到達した時点で探索を終了し、記録しておいた親ノード情報をたどることで、最短パスを出力します。

アルゴリズムのポイント

幅優先探索（BFS）はレベルごとにノードを訪問するため、最初に見つかった葉ノードが必ず最短パスの終点となります。各ノードの親の値をハッシュマップ（unordered_map）に記録しておけば、葉ノードから根ノードへ遡ってパスを再構築できます。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
struct Node{
    struct Node* left;
    struct Node* right;
    int data;
};
struct Node* create_node(int data){
    struct Node* temp = new Node;
    temp->data = data;
    temp->left = NULL;
    temp->right = NULL;
    return temp;
}
void print_spath(int Data, unordered_map<int, int> parent){
    if (parent[Data] == Data)
        return;
    print_spath(parent[Data], parent);
    cout << parent[Data] << " ";
}
void leftmost_path(struct Node* root){
    queue<struct Node*> q;
    q.push(root);
    int LeafData = -1;
    struct Node* temp = NULL;
    unordered_map<int, int> parent;
    parent[root->data] = root->data;
    while (!q.empty()){
        temp = q.front();
        q.pop();
        if (!temp->left && !temp->right){
            LeafData = temp->data;
            break;
        }
        else{
            if (temp->left){
                q.push(temp->left);
                parent[temp->left->data] = temp->data;
            }
            if (temp->right) {
                q.push(temp->right);
                parent[temp->right->data] = temp->data;
            }
        }
    }
    print_spath(LeafData, parent);
    cout << LeafData << " ";
}
int main(){
    struct Node* root = create_node(21);
    root->left = create_node(24);
    root->right = create_node(35);
    root->left->left = create_node(44);
    root->right->left = create_node(53);
    root->right->right = create_node(71);
    root->left->left->left = create_node(110);
    root->left->left->right = create_node(91);
    root->right->right->left = create_node(85);
    leftmost_path(root);
    return 0;
}

実行結果

21 35 53

コードの解説

このサンプルでは、根ノード21から始まる二分木を構築しています。幅優先探索により、最初に見つかった葉ノードは53です。53に到達するまでのパスは「21 → 35 → 53」となり、これが出力結果として表示されます。

処理の流れ：

1. 根ノードをキューに追加し、親マップに自分自身を登録します。
2. キューからノードを取り出し、左右の子が存在しない場合、そのノードを葉として記録し探索を終了します。
3. 子が存在する場合は、子ノードをキューに追加するとともに、親マップに「子の値 → 親の値」の対応を記録します。
4. 葉ノードが見つかったら、再帰関数 print_spath を使って親マップを遡り、根ノードから順にパスを出力します。

このアルゴリズムの計算量は、ノード数をNとすると時間計算量O(N)、空間計算量O(N)となります。全ノードの深さを比較する必要がないため、深さ優先探索よりも効率的に最短パスを求められる点が大きな利点です。