C++で二分木の特定ノードから距離Kにあるすべてのノードを出力する方法

問題の概要

本記事では、二分木・ターゲットノード・整数Kが与えられたとき、ターゲットノードから距離Kにあるすべてのノードを出力するアルゴリズムをC++で実装して解説します。

二分木(Binary Tree)とは、各ノードが最大2つの子ノード(0個・1個・2個)を持つことができる特殊な木構造です。

問題例

まず、具体例を使って問題を理解しましょう。下図のような二分木を考えます。

• K = 2
• ターゲットノード: 9

出力:

5 1 3

説明:

ここでいう「距離」は、ターゲットノードより上の階層・下の階層・同じ階層のいずれのノードに対しても定義されます。そのため、方向を問わず距離Kにあるノードをすべて出力する必要があります。

解法のアプローチ

この問題を解くには、ターゲットノードから距離Kにあるノードがどのように分類されるかを理解することが重要です。先ほどの例から、該当するノードは次の2種類に分けられます。

1. ターゲットノード自身の部分木に含まれるノード(例: 5 と 1)
2. ターゲットノードの祖先の部分木に含まれるノード(例: 3)

ケース1: ターゲットノードの部分木内を探索

最初のケースでは、ターゲットノードの部分木を走査し、各ノードがターゲットからちょうど距離Kにあるかどうかを判定します。条件を満たすノードが見つかったら出力します。

ケース2: 祖先ノード経由で探索

2番目のケースでは、ターゲットノードの祖先ノードをたどりながら、各祖先のもう一方の側(ターゲットを含まない部分木)を調べ、ターゲットから距離Kとなるノードを出力します。祖先までの距離と残りの距離を組み合わせることで、正確に判定できます。

C++での実装

以下のプログラムは、上述の解法を実装したものです。

サンプルコード

#include <iostream>
using namespace std;
struct node {
    int data;
    struct node *left, *right;
};
// ターゲットノードの部分木内で距離kのノードを出力
void printSubtreeNodes(node *root, int k) {
    if (root == NULL || k < 0) return;
    if (k == 0){
        cout << root->data << "\t";
        return;
    }
    printSubtreeNodes(root->left, k-1);
    printSubtreeNodes(root->right, k-1);
}
// ターゲットから距離kのすべてのノードを出力
int printKNodes(node* root, node* target, int k){
    if (root == NULL) return -1;
    if (root == target){
        printSubtreeNodes(root, k);
        return 0;
    }
    int dl = printKNodes(root->left, target, k);
    if (dl != -1){
        if (dl + 1 == k)
            cout << root->data << "\t";
        else
            printSubtreeNodes(root->right, k-dl-2);
        return 1 + dl;
    }
    int dr = printKNodes(root->right, target, k);
    if (dr != -1){
        if (dr + 1 == k)
            cout << root->data << endl;
        else
            printSubtreeNodes(root->left, k-dr-2);
        return 1 + dr;
    }
    return -1;
}
node *insertNode(int data){
    node *temp = new node;
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}
int main(){
    node * root = insertNode(6);
    root->left = insertNode(3);
    root->right = insertNode(9);
    root->left->right = insertNode(4);
    root->right->left = insertNode(8);
    root->right->right = insertNode(10);
    root->right->right->left = insertNode(5);
    root->right->right->right = insertNode(1);
    node * target = root->right;
    int K = 2;
    cout << "Nodes at distance " << K << " from the target node are :\n";
    printKNodes(root, target, K);
    return 0;
}

実行結果

Nodes at distance 2 from the target node are −
5 1 3

計算量の評価

このアルゴリズムは木の各ノードを高々一度ずつ訪問するため、時間計算量は O(N)(Nはノード総数)です。また、空間計算量は再帰呼び出しのスタック深さに依存し、木が偏っている最悪ケースでは O(N)、バランスの取れた木では O(log N) となります。

まとめ

ターゲットノードから距離Kにあるノードは、「ターゲットの部分木内」および「祖先の反対側の部分木内」の2パターンに分けて探索することで効率的に求められます。再帰関数がターゲットノードまでの距離を返り値として伝播させることで、祖先側の探索もシンプルに実装できる点がポイントです。