C++で二分木の各階層における最大値を見つける方法

二分木が与えられたとき、その木の各階層(レベル)ごとの最大値を求めることを考えます。例えば、次のような二分木があるとします。

この場合、出力は [1, 3, 9] となります。

• ルート(最上位)の階層には「1」だけが存在するため、最大値は 1
• 第1階層には「3」と「2」があり、最大値は 3
• 第2階層には「5」「3」「9」があり、最大値は 9

解決のためのアプローチ

この問題は、再帰的な深さ優先探索(DFS) を使うことで簡潔に解くことができます。手順は以下の通りです。

1. 結果を格納するための配列 ans を定義します。
2. 再帰関数 solve() を定義します。この関数はツリーノードとレベル(初期値は 0)を引数として受け取ります。
3. ノードが null の場合は何もせずに return します。
4. 現在のレベルが ans のサイズと等しい場合(= その階層に初めて到達した場合)、ノードの値を ans に追加します。そうでなければ、ans[level] とノードの値を比較し、大きい方で更新します。
5. 左部分木に対して solve(node->left, level + 1) を呼び出します。
6. 右部分木に対して solve(node->right, level + 1) を呼び出します。
7. メイン関数からは、ルートノードとレベル 0 を引数として solve() を呼び出します。
8. 最後に ans を返します。

この方法では、各階層に最初に到達した時点でその階層の値を記録し、以降同じ階層のノードに出会うたびに最大値を更新していくため、幅優先探索(BFS)のようにキューを管理する必要がなく、シンプルな実装になります。

C++での実装例

以下のコードで実際の動作を確認してみましょう。

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> 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 = NULL;
        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:
    vector <int> ans;
    void solve(TreeNode* node, int level = 0){
        if(!node)return;
        if(level == ans.size()){
            ans.push_back(node->val);
        } else {
            ans[level] = max(ans[level], node->val);
        }
        solve(node->left, level + 1);
        solve(node->right, level + 1);
    }
    vector<int> largestValues(TreeNode* root) {
        solve(root);
        return ans;
    }
};
main(){
    vector<int> v = {1,3,2,5,3,NULL,9};
    TreeNode *tree = make_tree(v);
    Solution ob;
    print_vector(ob.largestValues(tree));
}

入力

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

出力

[1, 3, 9]

計算量について

• 時間計算量: O(n) ― 木のすべてのノードを一度ずつ訪問するためです。
• 空間計算量: O(h) ― 再帰の深さは木の高さ h に依存します(最悪の場合、木が偏っていると O(n) になります)。

このように、再帰DFSを活用することで、各階層の最大値を効率よく求めることができます。