C++で二分木における最も深い奇数レベルノードの深さを求める方法

このチュートリアルでは、C++を使って二分木（バイナリツリー）の中から最も深い奇数レベルにあるノードの深さを求める方法を学びます。

これは二分木の深さを求める処理とよく似ています。ただし、今回は「現在のレベルが奇数であるかどうか」という条件が1つ追加される点が異なります。

それでは、問題を解くための手順を順番に見ていきましょう。

• ダミーデータを使って二分木を初期化します。

• 二分木の中で最も深い奇数レベルのノードを見つけるための再帰関数を作成します。

  • 現在のノードが葉ノードであり、かつそのレベルが奇数の場合は、現在のレベルを返します。

  • それ以外の場合は、左の子ノードと右の子ノードに対して再帰的に関数を呼び出し、その結果の最大値を返します。

• 最も深い奇数レベルのノードの深さを出力します。

コード例

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

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    struct Node *left, *right;
};
struct Node* newNode(int data) {
    struct Node* node = (struct Node*) malloc(sizeof(struct Node));
    node->data = data;
    node->left = node->right = NULL;
    return node;
}
int oddLeafDepthInTree(struct Node *root, int level) {
    if (root == NULL) {
        return 0;
    }
    if (root->left == NULL && root->right == NULL && level % 2 == 1) {
        return level;
    }
    return max(oddLeafDepthInTree(root->left, level + 1), oddLeafDepthInTree(root->right, level + 1));
}
int main() {
    struct Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->right->left = newNode(5);
    root->right->right = newNode(6);
    root->right->left->right = newNode(7);
    root->right->right->right = newNode(8);
    int level = 1, depth = 0;
    cout << oddLeafDepthInTree(root, level) << endl;
    return 0;
}

実行結果

上記のコードを実行すると、以下のような結果が出力されます。

3

まとめ

このチュートリアルでは、再帰関数を活用して二分木の中で最も深い奇数レベルにあるノードの深さを求める方法を解説しました。ポイントは、葉ノードに到達した時点でレベルの偶奇を判定し、奇数であればそのレベルを候補として返すことです。本チュートリアルについてご質問がある場合は、ぜひコメント欄でお知らせください。