C++で二分木の右側面図（右サイドビュー）を求めるアルゴリズムと実装方法

はじめに

二分木があるとき、その木を右側から見ると、特定のノードだけが見えます。この問題では、右側から見えるノードの値をすべて出力することが求められます。

例えば、次のような二分木を考えてみましょう。

この場合、右側から見えるのは 1 → 3 → 4 の順になります。それでは、この問題を解くためのアプローチを見ていきましょう。

解法のアプローチ：DFS（深さ優先探索）を使う

この問題は、DFS（深さ優先探索）を工夫して使うことで効率的に解けます。ポイントは「各レベルで最初に到達したノード＝右端のノード」という性質を利用することです。

手順

• まず、DFS用のヘルパーメソッドを作成します。引数として、ツリーノード、結果を格納する配列、現在のレベルを受け取ります。レベルの初期値は 0 です。
• ノードが null の場合は何もせず return します。
• 現在のレベルが答えの配列の長さと等しい場合、そのノードは「そのレベルで最初に訪れた（＝最も右にある）ノード」なので、値を答えの配列に挿入します。
• 続いて、右の子ノードに対して dfs(右の子, ans, level + 1) を呼び出します。
• その後、左の子ノードに対して dfs(左の子, ans, level + 1) を呼び出します。

重要なのは、必ず右側を先に探索することです。こうすることで、各レベルで最初に訪れるノードが常に右端のノードになります。

メイン関数での呼び出し

メイン関数からは、木のルートノードと空の配列を使って dfs(root, ans) を呼び出します。レベルの初期値は 0 です。

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;
        }
};
void insert(TreeNode **root, int val){
    queue<TreeNode*> q;
    q.push(*root);
    while(q.size()){
        TreeNode *temp = q.front();
        q.pop();
        if(!temp->left){
            if(val != NULL)
                temp->left = new TreeNode(val);
            else
                temp->left = new TreeNode(0);
            return;
        } else {
            q.push(temp->left);
        }
        if(!temp->right){
            if(val != NULL)
            temp->right = new TreeNode(val);
        else
            temp->right = new TreeNode(0);
            return;
        } else {
            q.push(temp->right);
        }
    }
}
TreeNode *make_tree(vector<int> v){
    TreeNode *root = new TreeNode(v[0]);
    for(int i = 1; i<v.size(); i++){
        insert(&root, v[i]);
    }
    return root;
}
class Solution {
    public:
    void dfs(TreeNode* node, vector <int>& ans, int level = 0){
        if(!node) return;
        if(level == ans.size())ans.push_back(node->val);
        dfs(node->right, ans, level + 1);
        dfs(node->left, ans, level + 1);
    }
    vector<int> rightSideView(TreeNode* root) {
        vector <int> ans;
        dfs(root, ans);
        return ans;
    }
};
main(){
    vector<int> v = {1,2,3,NULL,5,NULL,4};
    TreeNode *root = make_tree(v);
    Solution ob;
    print_vector(ob.rightSideView(root));
}

実行結果

入力

[1,2,3,null,5,null,4]

出力

[1, 3, 4]

コードの解説

• make_tree / insert 関数： 配列形式のデータから二分木を構築するための補助関数です。キューを使った幅優先の方法でノードを挿入していきます。
• dfs 関数： 右の子を先に再帰的に探索することで、各レベルで最初に到達するノードが右端のノードになります。level が ans.size() と一致したタイミングで値を追加します。
• rightSideView 関数： 空の結果配列を用意し、ルートから DFS を開始して、右側から見えるノードの値のリストを返します。

計算量

• 時間計算量： O(n) — 各ノードを一度ずつ訪問します（n はノード数）。
• 空間計算量： O(h) — 再帰の深さは木の高さ h に依存します（最悪の場合 O(n)）。

まとめ

二分木の右側面図を求める問題は、「右側を優先して DFS を行い、各レベルで最初に訪れたノードを記録する」というシンプルな発想で解決できます。BFS（幅優先探索）を使って各レベルの最後の要素を取る方法もありますが、DFS を使うとコードがより簡潔になります。ぜひ自分でも実装して理解を深めてみてください。