C++で二分木の左側の葉ノードの合計を求める方法

ルートノードとその左の子・右の子を持つ二分木を考えます。この記事での課題は、親ノードから見て左側の子となっている葉ノード(左葉ノード)の値の合計を求めることです。

例

入力:

出力:

15

説明: 入力された二分木において、親に対して左の子となっている葉ノードは 9、4、2 の3つです。したがって合計は 9+4+2 = 15 となり、出力は 15 になります。

この問題へのアプローチ

二分木が与えられたとき、親に対して左の子となっているすべての葉ノードの合計を求めるのが目的です。

この問題は再帰を使うことで効率的に解けます。基本的な考え方は次のとおりです。まず現在のノードの左の子が存在するかを確認し、その左の子が葉ノード(子を一切持たないノード)であれば、その値を合計に加算します。右部分木に対しては再帰的に同じ処理を適用します。この操作をすべてのノードに対して繰り返すことで、木全体の左葉ノードの合計が求まります。

アルゴリズムの手順

• ルートノードとその左右の子を持つ二分木を入力として受け取ります。
• 整数型関数 leftLeafSum(treenode* root) は、ルートノードを引数に取り、親に対して左の子となっているすべての葉ノードの合計を返します。
• ルートノードが NULL(空)の場合は 0 を返します。そうでなければ、ルートの左の子を調べます。
• ルートの左の子が子を持たない(= 葉ノードである)場合は、その値を加算し、続いて右部分木に対して再帰的に処理を行います。
• 最後に、左部分木と右部分木それぞれの再帰呼び出しの結果を合計して返します。

C++による実装例

#include <bits/stdc++.h>
using namespace std;

struct treenode {
    int data;
    treenode *left;
    treenode *right;
};

struct treenode *createNode(int d) {
    struct treenode *root = new treenode;
    root->data = d;
    root->left = NULL;
    root->right = NULL;
    return root;
}

int leftLeafSum(treenode *root) {
    if (root == NULL) {
        return 0;
    }
    // 左の子が存在し、かつそれが葉ノードの場合
    if (root->left && !root->left->left && !root->left->right) {
        return root->left->data + leftLeafSum(root->right);
    }
    return leftLeafSum(root->left) + leftLeafSum(root->right);
}

int main() {
    struct treenode *root = NULL;
    root = createNode(4);
    root->left = createNode(2);
    root->right = createNode(2);
    root->left->right = createNode(7);
    root->left->left = createNode(5);
    root->right->left = createNode(5);
    root->right->right = createNode(7);

    int sum = leftLeafSum(root);
    cout << sum << endl;
    return 0;
}

上記のコードを実行すると、次の出力が得られます。

出力

10

説明: この例では、親に対して左の子となっている葉ノードは 5 と 5 の2つだけです(7 などの他のノードは右側の子や内部ノードのため対象外)。したがって、左葉ノードの合計は 5+5 = 10 となります。