C++で親配列で表現された二分木の高さを求める方法

この問題では、木構造を表すサイズ n の配列 arr[] が与えられます。ここでの課題は、親配列で表現された二分木の高さを求めることです。

二分木とは、各ノードが最大2つの子ノードを持つことができる木構造のデータ構造です。本問題では、配列の各要素 arr[i] が「インデックス i のノードの親ノードのインデックス」を意味し、根ノードのみ arr[i] = -1 として表されます。

木の高さとは、根ノードから最も遠い葉ノードまで移動する際に通過するノードの数のことです。

解決アプローチ

この問題に対する単純な解決策は、親配列から木を実際に構築する方法です。まず木の根を特定し、そのインデックスに対して左部分木と右部分木を再帰的に構築していき、最大の高さを返します。

より効率的な方法は、配列から各ノードの根からの深さを計算し、それを深さ配列(depth array)に格納しておくことです。あとはこの配列から最大の深さを返せば、それが木の高さになります。

深さ計算の流れ

• ノード i の深さがすでに計算済みであれば、再計算せずにその値を利用します。
• arr[i] == -1 の場合、ノード i は根なので深さは 1 となります。
• それ以外の場合は、先に親ノード arr[i] の深さを求め、ノード i の深さは「親の深さ + 1」として計算します。

解決策の動作を示すプログラム

例

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

// 各ノードの深さを求める再帰関数
void findAllDepths(int arr[], int i, int nodeDepth[]) {
    // すでに深さが計算されていれば何もしない
    if (nodeDepth[i])
        return;
    // 根ノードの場合、深さは 1
    if (arr[i] == -1) {
        nodeDepth[i] = 1;
        return;
    }
    // 親ノードの深さを先に計算
    if (nodeDepth[arr[i]] == 0)
        findAllDepths(arr, arr[i], nodeDepth);
    // 自分の深さ = 親の深さ + 1
    nodeDepth[i] = nodeDepth[arr[i]] + 1;
}

int findMaxHeightBT(int arr[], int n) {
    int nodeDepth[n];
    for (int i = 0; i < n; i++)
        nodeDepth[i] = 0;
    // 全ノードの深さを計算
    for (int i = 0; i < n; i++)
        findAllDepths(arr, i, nodeDepth);
    // 最大の深さ(= 木の高さ)を求める
    int maxHeight = nodeDepth[0];
    for (int i = 1; i < n; i++)
        if (maxHeight < nodeDepth[i])
            maxHeight = nodeDepth[i];
    return maxHeight;
}

int main() {
    int arr[] = {-1, 0, 0, 1, 1};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout<<"二分木の最大の高さは "<<findMaxHeightBT(arr, n);
    return 0;
}

出力 −

二分木の最大の高さは 3

コードの解説

入力配列 {-1, 0, 0, 1, 1} の場合、木は次のように構成されます。

• ノード 0 が根(arr[0] = -1)
• ノード 0 の子はノード 1 とノード 2
• ノード 1 の子はノード 3 とノード 4

最も深い経路は「ノード 0 → ノード 1 → ノード 3」となり、通過するノード数が 3 であるため、木の高さは 3 と求まります。

この手法では、各ノードの深さ計算がそれぞれ一度だけ行われるため、時間計算量は O(n) となり、非常に効率的です。メモ化により無駄な再帰呼び出しを避けている点もポイントです。