C++で二分木をレベル順（幅優先順）に走査するプログラムの実装方法

二分木が与えられたとき、それをレベル順（幅優先順）で走査することを考えます。例えば、次のような二分木があるとしましょう。

この場合、レベル順走査による訪問順序は [1, 2, 3, 5, 4] となります。上から順に、同じ深さのノードは左から右へと処理していくイメージです。

アルゴリズムの考え方

レベル順走査を実現するには、キュー（FIFO：先入れ先出し） を利用するのが定番のアプローチです。手順は以下の通りです。

• ノードを格納するためのキューを用意する
• ルートノードをキューに挿入する
• キューが空になるまで、以下の処理を繰り返す
  • キューの先頭にあるノードを参照する
  • そのノードの値を出力（または結果リストに記録）する
  • 左の子が存在すれば、キューに追加する
  • 右の子が存在すれば、キューに追加する
  • キューの先頭要素を取り除く

この方法では、各ノードはちょうど1回ずつ処理されるため、計算量はノード数を n として O(n) になります。また、最悪の場合（完全二分木など）キューには最大で木の幅に相当するノードが保持されるため、空間計算量も O(n) です。

C++での実装例

それでは、実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<int> v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
       cout << v[i] << ", ";
    }
    cout << "]"<<endl;
}
class TreeNode{
    public:
       int val;
       TreeNode *left, *right;
       TreeNode(int data){
          val = data;
          left = right = NULL;
       }
};
class Solution {
    public:
    vector<int> solve(TreeNode* root) {
       if(!root)
          return {};
       vector <int> ret;
       queue <TreeNode*> q;
       q.push(root);
       while(!q.empty()){
          TreeNode* node = q.front();
          q.pop();
          ret.push_back(node->val);
          if(node->left){
             q.push(node->left);
          }
          if(node->right){
             q.push(node->right);
          }
       }
       return ret;
    }
};
main(){
    TreeNode *root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->right = new TreeNode(5);
    root->right->right = new TreeNode(4);
    Solution ob;
    print_vector(ob.solve(root));
}

コードのポイント

• TreeNodeクラス：ノードの値 val と左右の子ポインタ left / right を持ちます。
• Solve関数：ルートが null の場合は空のベクトルを返し、そうでなければキューを使って幅優先に値を収集します。
• print_vector関数：結果を見やすい形式で出力するための補助関数です。

入力

TreeNode *root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->right = new TreeNode(5);
root->right->right = new TreeNode(4);

出力

[1, 2, 3, 5, 4]

このように、キューを活用することで二分木のレベル順走査をシンプルかつ効率的に実装できます。幅優先探索（BFS）の基本的なパターンでもあるため、木やグラフの問題全般に応用できる重要なテクニックです。