C++で木構造のノード数が奇数・偶数となるレベルをすべて出力する方法

この記事では、木（ツリー）構造が与えられたときに、各レベルに含まれるノードの数を調べ、その数が奇数であるレベルと偶数であるレベルをそれぞれ出力する方法を、C++のサンプルコード付きで解説します。

問題の概要

まず、具体的な例を使って概念を確認しましょう。次のような木構造を考えます。

出力：

ノード数が奇数のレベル：1, 3, 4
ノード数が偶数のレベル：2

解説： 第1レベルにはノードが1個（奇数）、第2レベルには2個（偶数）、第3レベルには3個（奇数）、第4レベルには1個（奇数）存在します。そのため、奇数となるのは「1, 3, 4」のレベル、偶数となるのは「2」のレベルです。

解き方のアプローチ

この問題を解くには、まず各レベルにいくつのノードが存在するかを数え、その結果をもとに奇数レベルと偶数レベルを判定して出力します。

具体的には、以下の手順で処理を進めます。

1. ステップ1： 「height[node] = 1 + height[parent]」という関係式を利用し、DFS（深さ優先探索）によって各ノードの高さ（レベル）を求めます。
2. ステップ2： 各レベルに属するノードの個数を配列に記録していきます。
3. ステップ3： 記録した配列を走査し、ノード数が奇数のレベルと偶数のレベルをそれぞれ出力します。

C++による実装例

#include <bits/stdc++.h>
using namespace std;

// 木を巡回して各ノードの高さ（レベル）を求める
void traversal(int node, int parent, int height[], int vis[], vector<int> tree[]){
    height[node] = 1 + height[parent];
    vis[node] = 1;
    for (auto it : tree[node]) {
        if (!vis[it]) {
            traversal(it, node, height, vis, tree);
        }
    }
}

// 無向木に辺を追加する
void insert(int x, int y, vector<int> tree[]){
    tree[x].push_back(y);
    tree[y].push_back(x);
}

// 奇数レベルと偶数レベルを出力する
void evenOddLevels(int N, int vis[], int height[]){
    int mark[N + 1];
    memset(mark, 0, sizeof mark);
    int maxLevel = 0;
    for (int i = 1; i <= N; i++) {
        if (vis[i])
            mark[height[i]]++;
        maxLevel = max(height[i], maxLevel);
    }
    cout << "ノード数が奇数のレベル：";
    for (int i = 1; i <= maxLevel; i++) {
        if (mark[i] % 2)
            cout << i << " ";
    }
    cout << "\nノード数が偶数のレベル：";
    for (int i = 1; i <= maxLevel; i++) {
        if (mark[i] % 2 == 0)
            cout << i << " ";
    }
}

int main(){
    const int N = 9;
    vector<int> tree[N + 1];
    insert(1, 2, tree);
    insert(1, 3, tree);
    insert(2, 4, tree);
    insert(2, 5, tree);
    insert(5, 7, tree);
    insert(5, 8, tree);
    insert(3, 6, tree);
    insert(6, 9, tree);

    int height[N + 1];
    int vis[N + 1] = { 0 };
    height[0] = 0;

    traversal(1, 0, height, vis, tree);
    evenOddLevels(N, vis, height);

    return 0;
}

コードのポイント

• traversal関数： 親ノードの高さに1を加えることで、各ノードが何番目のレベルに属するかを再帰的に求めます。
• mark配列： mark[レベル] に、そのレベルに存在するノード数をカウントして格納します。
• evenOddLevels関数： 各レベルのノード数を2で割った余りを判定し、奇数・偶数に分けて出力します。

実行結果

ノード数が奇数のレベル：1 3 4
ノード数が偶数のレベル：2

計算量について

このアルゴリズムは木の全ノードを一度ずつ訪問するため、時間計算量は O(N) です。また、各ノードの高さやレベルごとのノード数を記録するために配列を使用するため、空間計算量も O(N) となります。