C++で二分木のすべての右ノードから最大値を見つける方法

この記事では、二分木（バイナリツリー）が与えられたときに、すべての右ノードの中から最大値を見つける方法を解説します。

問題の概要

与えられた二分木に含まれるすべての「右の子ノード」の値を調べ、その中で最大の値を求めるのが目的です。

入力例

以下のような二分木を考えてみましょう。

        5
       / \
      3   2
     / \ / \
    1  8 6  9

出力例

9

解説

この木における右の子ノードは {2, 8, 9} の3つです。これらの中で最大の値は 9 となります。

解決アプローチ

この問題は、木を再帰的に走査しながら解くことができます。基本的な考え方は以下のとおりです。

• 各ノードを訪問し、そのノードに右の子が存在するかどうかを確認します。
• 右の子が存在する場合は、その値を現在の最大値（maxRight）と比較し、より大きければ更新します。
• 左部分木と右部分木に対しても再帰的に同じ処理を行い、全体の最大値を求めます。

C++による実装例

それでは、実際のコードを見ていきましょう。

#include <iostream>
using namespace std;

struct Node {
    int data;
    struct Node *left, *right;
};

Node* newNode(int data) {
    Node* temp = new Node;
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}

int findMaxRightNode(Node* root) {
    int maxRight = -100;

    if (root == NULL)
        return -1;

    if (root->right != NULL)
        maxRight = root->right->data;

    return max( findMaxRightNode(root->right),
                max(maxRight, findMaxRightNode(root->left)) );
}

int main() {
    Node* root = newNode(5);
    root->left = newNode(3);
    root->right = newNode(2);
    root->left->left = newNode(1);
    root->left->right = newNode(8);
    root->right->left = newNode(6);
    root->right->right = newNode(9);

    cout << "二分木のすべての右ノードの中の最大値は "
         << findMaxRightNode(root);

    return 0;
}

実行結果

二分木のすべての右ノードの中の最大値は 9

コードのポイント

• newNode関数： 新しいノードを作成し、左右の子ポインタをNULLで初期化するヘルパー関数です。
• findMaxRightNode関数： 再帰的に木を走査します。現在のノードに右の子があれば、その値をmaxRightに記録し、左部分木・右部分木の探索結果と比較して最大値を返します。
• 計算量： 各ノードを一度ずつ訪問するため、時間計算量はO(N)、Nはノード数です。

このように、シンプルな再帰処理を用いることで、二分木のすべての右ノードの中から効率的に最大値を見つけることができます。