C++で二分木のルートから特定ノードまでの距離を求める方法

二分木が与えられたとき、ルートから特定のノード u までの距離(経路の長さ)を求める問題を考えてみましょう。例として、次のような二分木を想定します。

この木において、ルートからノード6までの距離は2、ルートからノード8までの距離は3となります。

解決のアプローチ

この問題は、再帰的な手法を用いて解くことができます。具体的には、目的のノードを左部分木と右部分木の両方に対して再帰的に探索し、再帰の各段階(レベル)で距離を1ずつ加算していきます。

探索の仕組みは以下の通りです。

• 現在のノードがNULLの場合は -1 を返します(ノードが見つからなかったことを示す)。
• 現在のノードの値が目的の値と一致した場合、または左部分木・右部分木の再帰呼び出しの結果が 0 以上の場合、距離 + 1 を返します。
• どちらにも見つからなかった場合は -1 を返します。

このように、ノードが見つかった位置から再帰が戻るたびに距離が1ずつ加算されるため、ルートまで戻った時点で正確な距離が得られます。

実装例(C++)

#include<iostream>
using namespace std;

class Node {
    public:
        int data;
        Node *left, *right;
};

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

int getDistance(Node *root, int x) {
    if (root == NULL)
        return -1;
    int dist = -1;
    if ((root->data == x) || (dist = getDistance(root->left, x)) >= 0 || (dist = getDistance(root->right, x)) >= 0)
        return dist + 1;
    return dist;
}

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

    cout << "Distance from root to node 6 is: " << getDistance(root, 6);
    cout << "\nDistance from root to node 8 is: " << getDistance(root, 8);
}

実行結果

Distance from root to node 6 is: 2
Distance from root to node 8 is: 3

コードのポイント

• getDistance 関数では、短絡評価を活用することで、左部分木でノードが見つかった場合に右部分木の探索をスキップしています。
• 計算量は木のノード数を n とすると O(n) であり、最悪の場合すべてのノードを訪問します。
• 空間計算量は再帰の深さに依存し、木の高さが h の場合 O(h) となります。

この手法はシンプルでありながら効率的に動作し、任意の二分木におけるルートからノードまでの距離計算に応用できます。