C++で二分木における最も近い葉ノードまでの距離を求める方法

二分木が与えられ、その葉ノードはそれぞれ異なるレベルに存在するとします。さらに、あるノードを指すポインタが与えられ、そのノードから最も近い葉ノードまでの距離を求める必要があります。

例として、次のような二分木を考えてみましょう。

この木における葉ノードは 2、-2、6 の3つです。もしポインタがノード -5 を指している場合、-5 から最も近い葉ノードまでの距離は 1 となります。

解決のアプローチ

この問題を解くには、次の手順で考えます。

まず、指定されたノードを根とする部分木を走査し、その部分木内で最も近い葉ノードを見つけて距離を記録します。次に、木の根から全体を走査します。ノード x が左部分木に存在する場合は右部分木側の葉を探索し、逆に右部分木に存在する場合は左部分木側の葉を探索します。これにより、指定ノードの祖先を経由して到達できる葉ノードも考慮した最小距離が求められます。

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;
}
void getLeafDownward(Node *root, int level, int *minDist) {
    if (root == NULL)
        return ;
    if (root->left == NULL && root->right == NULL) {
        if (level < (*minDist))
            *minDist = level;
        return;
    }
    getLeafDownward(root->left, level+1, minDist);
    getLeafDownward(root->right, level+1, minDist);
}
int getFromParent(Node * root, Node *x, int *minDist) {
    if (root == NULL)
        return -1;
    if (root == x)
        return 0;
    int l = getFromParent(root->left, x, minDist);
    if (l != -1) {
        getLeafDownward(root->right, l+2, minDist);
        return l+1;
    }
    int r = getFromParent(root->right, x, minDist);
    if (r != -1) {
        getLeafDownward(root->left, r+2, minDist);
        return r+1;
    }
    return -1;
}
int minimumDistance(Node *root, Node *x) {
    int minDist = INT8_MAX;
    getLeafDownward(x, 0, &minDist);
    getFromParent(root, x, &minDist);
    return minDist;
}
int main() {
    Node* root = getNode(4);
    root->left = getNode(2);
    root->right = getNode(-5);
    root->right->left = getNode(-2);
    root->right->right = getNode(6);
    Node *x = root->right;
    cout << "Closest distance of leaf from " << x->data <<" is: " << minimumDistance(root, x);
}

実行結果

Closest distance of leaf from -5 is: 1

コードの解説

この実装では、主に3つの関数が連携して動作します。

getLeafDownward は、指定されたノードから下方向へ再帰的に走査し、葉ノードに到達した時点での深さ（レベル）が現在の最小距離より小さければ更新します。

getFromParent は、根から目的のノード x を探索します。x が見つかった位置から遡りながら、その兄弟部分木に含まれる葉ノードまでの距離を計算し、最小距離の候補として記録します。

minimumDistance は、まず指定ノード自身の部分木内の最短距離を求め、次に祖先経由で到達できる葉ノードの距離も考慮することで、最終的な最小距離を返します。

このアルゴリズムにより、指定されたノードから最も近い葉ノードまでの距離を効率的に求めることができます。