C++で二分木の2つのノード間の距離を求めるプログラムの作成方法

この記事では、二分木（バイナリツリー）と木の中の2つのノードが与えられたときに、それらのノード間の距離を求めるC++プログラムの作成方法を解説します。

問題の概要

ここでいう「2つのノード間の距離」とは、一方のノードからもう一方のノードへ移動する際に通過する辺（エッジ）の最小本数のことを指します。

具体例を挙げて、問題を確認してみましょう。

入力

二分木

Node1 = 3、Node2 = 5

出力

3

出力の解説

ノード3からノード5までの経路は「3 → 1 → 2 → 5」です。この経路で通過する辺は3本であるため、2つのノード間の距離は3となります。

解法のアプローチ

この問題に対する基本的な解法は、最小共通祖先（LCA: Lowest Common Ancestor）を利用する方法です。2つのノードの共通祖先のうち、最も深い位置にあるノード（LCA）を求めたうえで、次の式に当てはめることで距離を計算できます。

distance(node1, node2) = distance(root, node1) + distance(root, node2) − 2 × distance(root, LCA)

ここで、distance(root, X) は根からノードXまでの距離（レベル）を表します。LCAを基準に考えることで、2つのノードを結ぶ経路上の辺の本数を効率よく求めることができます。

C++による実装例

#include <iostream>
using namespace std;

// 二分木のノードを表す構造体
struct Node {
    struct Node *left, *right;
    int key;
};

// 新しいノードを作成して返す関数
Node* insertNode(int key){
    Node *temp = new Node;
    temp->key = key;
    temp->left = temp->right = NULL;
    return temp;
}

// 指定した値を持つノードのレベル（深さ）を求める関数
int calcNodeLevel(Node *root, int val, int level) {
    if (root == NULL)
        return -1;
    if (root->key == val)
        return level;
    int lvl = calcNodeLevel(root->left, val, level+1);
    return (lvl != -1) ? lvl : calcNodeLevel(root->right, val, level+1);
}

// LCAを探索しながら各ノードのレベルと距離を記録する再帰関数
Node *findDistanceRec(Node* root, int node1, int node2, int &dist1, int &dist2, int &dist, int lvl){
    if (root == NULL) return NULL;
    if (root->key == node1){
        dist1 = lvl;
        return root;
    }
    if (root->key == node2){
        dist2 = lvl;
        return root;
    }
    Node *leftLCA = findDistanceRec(root->left, node1, node2, dist1, dist2, dist, lvl+1);
    Node *rightLCA = findDistanceRec(root->right, node1, node2, dist1, dist2, dist, lvl+1);
    // 左右の部分木それぞれでノードが見つかった場合、現在のノードがLCA
    if (leftLCA && rightLCA){
        dist = dist1 + dist2 - 2*lvl;
        return root;
    }
    return (leftLCA != NULL) ? leftLCA : rightLCA;
}

// 2つのノード間の距離を計算する関数
int CalcNodeDistance(Node *root, int node1, int node2) {
    int dist1 = -1, dist2 = -1, dist;
    Node *lca = findDistanceRec(root, node1, node2, dist1, dist2, dist, 1);
    // 両方のノードが見つかった場合は、LCAで計算済みの距離を返す
    if (dist1 != -1 && dist2 != -1)
        return dist;
    // 片方のノードがもう片方の祖先になっている場合
    if (dist1 != -1){
        dist = calcNodeLevel(lca, node2, 0);
        return dist;
    }
    if (dist2 != -1){
        dist = calcNodeLevel(lca, node1, 0);
        return dist;
    }
    return -1;
}

int main(){
    Node * root = insertNode(1);
    root->left = insertNode(2);
    root->right = insertNode(3);
    root->left->left = insertNode(4);
    root->left->right = insertNode(5);
    root->right->left = insertNode(6);
    cout << "値5のノードと値3のノードの間の距離は " << CalcNodeDistance(root, 3, 5);
    return 0;
}

実行結果

値5のノードと値3のノードの間の距離は 3

計算量

• 時間計算量：O(n)（nは木のノード数。すべてのノードを最大1回ずつ訪問するため）
• 空間計算量：O(h)（hは木の高さ。再帰呼び出しのスタックが使用する領域）

まとめ

二分木における2つのノード間の距離は、最小共通祖先（LCA）を求めることで効率的に計算できます。「根からの距離」と「LCAからの距離」を組み合わせるこの考え方は、木構造に関するさまざまな問題に応用できる重要なテクニックです。ぜひ仕組みを理解して、実際のプログラミングに活かしてください。