C++で二分木の最大値（または最小値）を求める方法

この記事では、二分木が与えられたときに、その中から最大値（または最小値）を持つノードを見つける方法を解説します。

問題の概要

与えられた二分木の中から、最大値および最小値を持つノードの値を求めるのが課題です。

入力例

出力例

max = 9 , min = 1

解法のアプローチ

二分木の最大値を求めるには、木全体を走査する必要があります。基本的な考え方は次のとおりです。

• ルートノードから出発し、再帰的に左部分木と右部分木を走査します。
• 各ノードにおいて、そのノードの値・左部分木の最大値・右部分木の最大値を比較します。
• 最も大きい値を現在の最大値として返し、再帰的に結果を親ノードへ伝えていきます。

この手法は深さ優先探索（DFS）に基づいており、葉ノードに到達した時点で再帰が終了し、各呼び出しがその部分木の最大値を返すことで、最終的に木全体の最大値が得られます。

計算量

• 時間計算量： O(N) — 各ノードを一度ずつ訪問します。
• 空間計算量： O(H) — 再帰呼び出しのスタックの深さは木の高さ H に依存します。

C++での実装例

以下は、この解法の動作を示すサンプルプログラムです。

#include <iostream>
using namespace std;

class Node {
    public:
        int data;
        Node *left, *right;

        Node(int data) {
            this->data = data;
            this->left = NULL;
            this->right = NULL;
        }
};

int findMaxNode(Node* root) {

    if (root == NULL)
        return -100;

    int maxVal = root->data;
    int leftMaxVal = findMaxNode(root->left);
    int rightMaxVal = findMaxNode(root->right);
    if (leftMaxVal > maxVal)
        maxVal = leftMaxVal;
    if (rightMaxVal > maxVal)
        maxVal = rightMaxVal;
    return maxVal;
}

int main() {

    Node* NewRoot = NULL;
    Node* root = new Node(5);
    root->left = new Node(3);
    root->right = new Node(2);
    root->left->left = new Node(1);
    root->left->right = new Node(8);
    root->right->left = new Node(6);
    root->right->right = new Node(9);
    cout<<"The Maximum element of Binary Tree is "<<findMaxNode(root) << endl;
    return 0;
}

実行結果

The Maximum element of Binary Tree is 9

補足：最小値を求める場合

最小値を求めたい場合は、比較の向きを逆にするだけで対応できます。具体的には、findMinNode 関数を作成し、左右の部分木の戻り値と現在のノードの値を比較して、より小さい方を採用するように変更します。また、NULLノード到達時の初期値も、-100 のような固定値ではなく INT_MAX を使うことで、より汎用的な実装になります。