C++で二分木の左側ビュー（左から見たノード一覧）を求めるプログラム

C++で二分木の左側ビューを求める方法

二分木が与えられたとき、その木を左側から見ると、一部のノードだけが目に入ります。本記事では、このようにして見えるノードの一覧（左側ビュー）を取得・表示するプログラムをC++で実装する方法を解説します。

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

この木を左側から見ると、ルートの 1、次の階層の 2、さらにその下の 5 が見えます。したがって、出力は [1, 2, 5] となります。

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

この問題は、深さ優先探索（DFS）を用いることで効率的に解けます。ポイントは、常に左側の子ノードから先に探索することです。こうすることで、各階層で最初に訪れるノードが、必ず左から見たときに見えるノードになります。

アルゴリズムの手順

• 結果を格納するための配列 ret を用意します。
• 関数 dfs() を定義します。引数としてノードと現在の深さ c（初期値は1）を受け取ります。
• ノードがNULLの場合は、何もせずにreturnします。
• c > lvl の場合（まだ訪れていない深さに到達した場合）：
  • lvl = c と更新します。
  • そのノードの値を ret に追加します。
• dfs(node->left, c + 1) を呼び出します。
• dfs(node->right, c + 1) を呼び出します。

メイン関数での処理

• lvl = -1 で初期化します。
• dfs(root, 0) を呼び出します。
• ret を返します。

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> ret;
    int lvl;
    void dfs(TreeNode* node, int c = 1){
        if(!node)
            return;
        if(c > lvl){
            lvl = c;
            ret.push_back(node->val);
        }
        dfs(node->left, c + 1);
        dfs(node->right, c + 1);
    }
    vector<int> solve(TreeNode* root) {
        lvl = -1;
        dfs(root, 0);
        return ret;
    }
};
int 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 *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,5]

仕組みの解説とまとめ

このアルゴリズムの鍵となるのは、変数 lvl の役割です。lvl は「これまでに処理した最大の深さ」を記録しており、まだ一度も訪れていない深さのノードに到達した瞬間だけ、そのノードの値を結果に追加します。左側の子を常に先に探索するため、各階層で最初に到達するノードが自動的に「左から見えるノード」になります。

計算量は、木のノード数をNとすると時間計算量 O(N)、再帰の深さに依存する空間計算量は O(H)（Hは木の高さ）です。また、同じ考え方は右側ビューの取得にも応用でき、その場合は右の子ノードを先に探索するだけで実現できます。