C++で二分木における最大長のサイクルを求めるアルゴリズムと実装例

問題の概要

二分木が与えられたとき、その木の中で形成できる最大長のサイクル（閉路）の長さを求めるのがこの記事のテーマです。基本的な考え方はシンプルで、根ノードから見た左部分木と右部分木それぞれの最大の高さを求め、その2つの最長パスを根ノードでつなぎ合わせることで、最も長いサイクルを構成します。

例えば次のような木の場合、最大長のサイクルは「1-2-3-4-7-6」または「1-6-7-4-3-2-1」となり、その長さは6になります。

入力例と出力例

例1

入力：次の二分木

出力：最大長のサイクルは 5

解説：左部分木の最大の高さは3、右部分木の最大の高さは1です。したがってサイクルの長さは 3＋1＋1＝5 となり、実際のサイクルは「1-2-3-4-6」または「1-6-4-3-2」です。

例2

入力：次の二分木

出力：最大長のサイクルは 7

解説：左部分木の最大の高さは3、右部分木の最大の高さも3です。したがってサイクルの長さは 3＋3＋1＝7 となり、実際のサイクルは「5-4-2-1-8-7-6」または「5-6-7-8-1-2-4-5」です。

アルゴリズムの流れ

このプログラムでは、以下の手順で最長サイクルを求めています。

• ノードの値（int data）と、左右の子ノードへのポインタを公開メンバとして持つ treenode クラスを定義します。
• newNode(int data) 関数は、受け取ったデータを持つ新しいノードを生成し、左右のポインタを NULL で初期化します。
• newNode() を呼び出して二分木を構築します。
• maxheight(treenode* root) 関数は、引数で渡されたノードを根とする木の最大の高さを返します。
• 根が NULL の場合は高さ0とみなし、0を返します。
• lheight と rheight には、再帰呼び出し maxheight(root->left) と maxheight(root->right) の結果として、左右部分木の高さが格納されます。
• 両者を比較し、大きい方の値に自分自身の分の1を加えて返します。
• main 関数内では、根の左部分木と右部分木の最大の高さをそれぞれ変数に保存します。
• 最大長のサイクルは、両者の和に根ノード自身を含めるための1を加えた maxlheight + maxrheight + 1 になります。
• 最後に、求めたサイクルの長さを出力します。

C++による実装例

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

// 木のノードを表すクラス
class treenode {
public:
    int data;
    treenode* left;
    treenode* right;
};

// 現在の根から見た左右部分木の高さの最大値を求める
int maxheight(treenode* root) {
    if (root == NULL)
        return 0;
    else {
        int lheight = maxheight(root->left);
        int rheight = maxheight(root->right);
        // 左右で高い方を採用する
        if (lheight > rheight)
            return (lheight + 1);
        else
            return (rheight + 1);
    }
}

// 新しいノードを生成する
treenode* newNode(int data) {
    treenode* Node = new treenode();
    Node->data = data;
    Node->left = NULL;
    Node->right = NULL;
    return (Node);
}

int main() {
    treenode* root = newNode(6);
    root->left = newNode(8);
    root->right = newNode(9);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->left->right->right = newNode(7);
    root->left->right->right->left = newNode(2);

    int maxlheight = maxheight(root->left);
    int maxrheight = maxheight(root->right);

    cout << "Maximum length cycle: " << maxlheight + maxrheight + 1;
    return 0;
}

実行結果

Maximum length cycle: 6

まとめ

このアルゴリズムは各ノードを一度だけ訪問するため、時間計算量は O(n)、空間計算量は再帰呼び出しのスタックを考慮すると最悪ケースで O(n) となります。「木の直径」を求める考え方と同じ原理で、根ノードを通る最長経路をサイクルとして捉えている点がポイントです。左部分木と右部分木の深さを正しく再帰的に計算できれば、あとは単純な足し算だけで答えが得られる、非常に効率的な手法といえます。