C++で二分木の最小深度を求めるアルゴリズムと実装方法

この記事では、二分木が与えられたときに、その最小深度（Minimum Depth）を求める問題について解説します。

二分木とは、各ノードが最大で2つの子ノードを持つことができる特別な木構造のことです。そして、二分木の最小深度とは、ルートノードから最も近い葉ノードまでの最短経路の長さを指します。

問題の例

具体的な例を使って問題を理解しましょう。

入力

        5
       / \
      2   9
     / \
    5   1
   / \
  7   3

出力

2

この例では、ルートノード「5」から葉ノード「9」までの経路の長さが2であり、これが最小深度となります。

解法アプローチ1：再帰による探索

最も基本的な解法は、二分木を走査しながら高さを数える方法です。各非葉ノードに対して子ノードを再帰的に呼び出し、葉ノードに到達した時点で1を返します。

重要なポイントとして、片方の子しか存在しないノードの場合、存在しない側の子を0として扱うと誤った結果になるため、存在する側の子のみを再帰的に探索する必要があります。

実装コード

#include<bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    struct Node* left, *right;
};
int findMinDepthBT(Node *currentNode) {
    if (currentNode == NULL)
        return 0;
    if (currentNode->left == NULL && currentNode->right == NULL)
        return 1;
    if (!currentNode->left)
        return findMinDepthBT(currentNode->right) + 1;
    if (!currentNode->right)
        return findMinDepthBT(currentNode->left) + 1;
    return min(findMinDepthBT(currentNode->left),
               findMinDepthBT(currentNode->right)) + 1;
}
Node *newNode(int data) {
    Node *temp = new Node;
    temp->data = data;
    temp->left = temp->right = NULL;
    return (temp);
}
int main() {
    Node *root = newNode(5);
    root->left = newNode(2);
    root->right = newNode(9);
    root->left->left = newNode(5);
    root->left->right = newNode(1);
    root->left->left->left = newNode(7);
    root->left->left->right = newNode(3);
    cout<<"The minimum depth of binary tree is "<<findMinDepthBT(root);
    return 0;
}

出力結果

The minimum depth of binary tree is 2

この再帰的なアプローチは十分に効率的ですが、より効果的に最小深度を求める他の走査手法もあります。

解法アプローチ2：レベル順走査（BFS）

もう一つの効率的なアプローチは、レベル順走査（幅優先探索・BFS）を利用する方法です。この手法では、木をレベルごと（上から順に）走査していき、最初に葉ノードに到達した時点でのレベル番号を返します。

幅優先探索では上のレベルから順に調べるため、最初に見つかった葉ノードが必ず最小深度のものとなり、木全体を走査せずに済むケースが多い点が利点です。

実装コード

#include<bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    struct Node *left, *right;
};
struct lOrderQueue {
    Node *node;
    int depth;
};
int findMinDepthBT(Node *root) {
    if (root == NULL)
        return 0;
    queue<lOrderQueue> levelOrder;
    lOrderQueue deQueue = {root, 1};
    levelOrder.push(deQueue);
    while (levelOrder.empty() == false) {
        deQueue = levelOrder.front();
        levelOrder.pop();
        Node *node = deQueue.node;
        int depth = deQueue.depth;
        if (node->left == NULL && node->right == NULL)
            return depth;
        if (node->left != NULL) {
            deQueue.node = node->left;
            deQueue.depth = depth + 1;
            levelOrder.push(deQueue);
        }
        if (node->right != NULL) {
            deQueue.node = node->right;
            deQueue.depth = depth+1;
            levelOrder.push(deQueue);
        }
    }
    return 0;
}
Node* newNode(int data) {
    Node *temp = new Node;
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}
int main() {
    Node *root = newNode(5);
    root->left = newNode(2);
    root->right = newNode(9);
    root->left->left = newNode(5);
    root->left->right = newNode(1);
    root->left->left->left = newNode(7);
    root->left->left->right = newNode(3);
    cout<<"The minimum depth of binary tree is "<<findMinDepthBT(root);
    return 0;
}

出力結果

The minimum depth of binary tree is 2

まとめ

二分木の最小深度を求めるには、主に以下の2つのアプローチがあります。

• 再帰（DFS）による方法： 実装がシンプルで直感的。計算量はO(N)。
• レベル順走査（BFS）による方法： 最小深度の葉ノードが浅い位置にある場合、早期に探索を終了できるため効率的。

どちらの手法も時間計算量はO(N)ですが、木の形状によってはBFSの方が実際の処理量を抑えられる場合があります。用途に応じて適切な手法を選択しましょう。