C++で二分木の2つの葉ノード間の最小パス合計を求める方法

問題文

各ノードが数値を持つ二分木が与えられます。この問題では、ある葉ノードから別の葉ノードまでのパスの合計として考えられる最小値を求めることがタスクです。

例

以下の二分木を見てみましょう。

この木における最小パスの合計は -6 です。具体的には、次の経路に対応します。

(-4) + 3 + 2 + (-8) + 1

アルゴリズム

この問題を解くポイントは、再帰呼び出しの中で次の2つの値を管理することです。

• 現在のノードを根とする部分木における「根から葉までの最小パス合計」
• 葉ノード同士を結ぶ「葉間の最小パス合計」

訪問した各ノードXに対して、Xの左部分木と右部分木それぞれの「根から葉までの最小合計」を求めます。次に、その2つの値にXのデータを加えた合計を計算し、現在記録している最小パス合計と比較します。より小さい値であれば、最小値を更新します。

なお、子を1つしか持たないノードでは葉と葉をつなぐパスが成立しないため、結果の更新は行わず、存在する側の子の合計をそのまま親へ返す点に注意してください。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
typedef struct node {
    int data;
    struct node *left;
    struct node *right;
} node;
node *newNode(int data) {
    node *n = new node;
    n->data = data;
    n->left = NULL;
    n->right = NULL;
    return n;
}
int getMinPath(node *root, int &result) {
    if (root == NULL) {
        return 0;
    }
    if (root->left == NULL && root->right == NULL) {
        return root->data;
    }
    int leftSum = getMinPath(root->left, result);
    int rightSum = getMinPath(root->right, result);
    if (root->left && root->right) {
        result = min(result, root->data + leftSum + rightSum);
        return min(root->data + leftSum, root->data + rightSum);
    }
    if (root->left == NULL) {
        return root->data + rightSum;
    } else {
        return root->data + leftSum;
    }
}
int getMinPath(node *root) {
    int result = INT_MAX;
    getMinPath(root, result);
    return result;
}
node *createTree() {
    node *root = newNode(2);
    root->left = newNode(3);
    root->right = newNode(-8);
    root->left->left = newNode(5);
    root->left->right = newNode(-4);
    root->right->left = newNode(1);
    root->right->right = newNode(10);
    return root;
}
int main() {
    node *root = createTree();
    cout << "Minimum sum path = " << getMinPath(root) << endl;
    return 0;
}

このアルゴリズムは各ノードを一度だけ訪問するため、計算量は O(n)、必要な追加メモリは再帰の深さに依存し O(h)(h は木の高さ)となります。

上記のプログラムをコンパイルして実行すると、次の出力が得られます。

出力

Minimum sum path = -6