C++で二分木内のすべての左葉の合計を求める方法【再帰・DFS・BFSで解説】

問題概要

この問題では、二分木が与えられ、その木に含まれるすべての「左葉（左の子である葉ノード）」の値の合計を求めることが課題となります。

具体例を使って問題を確認しましょう。

入力：

出力：11

説明−

木の左葉ノードは：2, 9
合計 = 2 + 9 = 11

ここで「左葉」とは、親ノードの左の子であり、かつ子を一切持たないノードを指します。上図の例では、ノード2とノード9がこの条件を満たすため、その合計値11が答えになります。

解決アプローチ 1：再帰

最もシンプルな解決策は、木をルートから葉へ向かって走査する方法です。走査の過程で、注目しているノードの左の子が葉ノードであれば、その値を合計に加算します。木全体の走査が完了した時点で、合計値を返して出力します。

実装例

この解法の動作を示すプログラムは以下の通りです。

#include <iostream>
using namespace std;
struct Node{
    int key;
    struct Node* left, *right;
};
Node *newNode(char k){
    Node *node = new Node;
    node->key = k;
    node->right = node->left = NULL;
    return node;
}
bool isLeafNode(Node *node){
    if (node == NULL)
        return false;
    if (node->left == NULL && node->right == NULL)
        return true;
    return false;
}
int findLeftLeavesSum(Node *root){
    int sum = 0;
    if (root != NULL){
        if (isLeafNode(root->left))
            sum += root->left->key;
        else
            sum += findLeftLeavesSum(root->left);
        sum += findLeftLeavesSum(root->right);
    }
    return sum;
}
int main(){
    struct Node *root = newNode(5);
    root->left = newNode(4);
    root->right = newNode(6);
    root->left->left = newNode(2);
    root->left->right = newNode(1);
    root->right->left = newNode(9);
    root->right->right = newNode(7);
    cout<<"The sum of left leaves of the tree is "<<findLeftLeavesSum(root);
    return 0;
}

出力

The sum of left leaves of the tree is 11

解決アプローチ 2：反復処理（スタックを使ったDFS）

次に、再帰を使わない反復処理によるアプローチを紹介します。スタックを用いて木を深さ優先探索（DFS）し、現在のノードの左の子が葉ノードかどうかを判定します。左葉であればその値を合計に加算し、そうでなければ何もしません。探索が完了したら合計を出力します。

実装例

この解法の動作を示すプログラムは以下の通りです。

#include<bits/stdc++.h>
using namespace std;
struct Node{
    int key;
    struct Node* left, *right;
};
Node *newNode(char k){
    Node *node = new Node;
    node->key = k;
    node->right = node->left = NULL;
    return node;
}
int findLeftLeavesSum(Node* root){
    if(root == NULL)
       return 0;
    stack<Node*> treeNodes;
    treeNodes.push(root);
    int sum = 0;
    while(treeNodes.size() > 0){
        Node* currentNode = treeNodes.top();
        treeNodes.pop();
        if (currentNode->left != NULL){
            treeNodes.push(currentNode->left);
            if(currentNode->left->left == NULL &&
            currentNode->left->right == NULL){
                sum += currentNode->left->key ;
            }
        }
        if (currentNode->right != NULL)
        treeNodes.push(currentNode->right);
    }
    return sum;
}
int main(){
    Node *root = newNode(5);
    root->left= newNode(4);
    root->right = newNode(6);
    root->left->left = newNode(2);
    root->left->right = newNode(1);
    root->right->left = newNode(9);
    root->right->right= newNode(7);
    cout<<"The sum of left leaves of the tree is "<<findLeftLeavesSum(root);
    return 0;
}

出力

The sum of left leaves of the tree is 11

解決アプローチ 3：BFS（幅優先探索）

3つ目のアプローチは、幅優先探索（BFS）を利用する方法です。キューには「ノードへのポインタ」と「そのノードが左の子であるかどうかを示すフラグ」をペアで格納します。取り出したノードが左の子であり、かつ葉ノードであれば、その値を合計に加算します。探索完了後、合計を出力します。

実装例

この解法の動作を示すプログラムは以下の通りです。

#include<bits/stdc++.h>
using namespace std;
struct Node{
    int key; struct Node* left, *right;
};
Node *newNode(char k){
    Node *node = new Node;
    node->key = k;
    node->right = node->left = NULL;
    return node;
}
int findLeftLeavesSum(Node* root) {
    if (root == NULL)
       return 0;
    queue<pair<Node*, bool> > leftTreeNodes;
    leftTreeNodes.push({ root, 0 });
    int sum = 0;
    while (!leftTreeNodes.empty()) {
        Node* temp = leftTreeNodes.front().first;
        bool is_left_child = leftTreeNodes.front().second;
        leftTreeNodes.pop();
        if (!temp->left && !temp->right && is_left_child)
           sum = sum + temp->key;
        if (temp->left) {
            leftTreeNodes.push({ temp->left, 1 });
        }
        if (temp->right) {
            leftTreeNodes.push({ temp->right, 0 });
        }
    }
    return sum;
}
int main(){
    Node *root = newNode(5);
    root->left= newNode(4);
    root->right = newNode(6);
    root->left->left = newNode(2);
    root->left->right = newNode(1);
    root->right->left = newNode(9);
    root->right->right= newNode(7);
    cout<<"The sum of left leaves of the tree is "<<findLeftLeavesSum(root);
    return 0;
}

出力

The sum of left leaves of the tree is 11

まとめ

今回紹介した3つのアプローチは、いずれも各ノードを一度だけ訪問するため、時間計算量は O(N)（Nはノード数）となります。空間計算量は、再帰では木の高さに依存して O(H)、スタックやキューを使用する反復処理では最大 O(N) となります。再帰コードは簡潔で理解しやすく、スタックやキューを使った手法は深い木においてスタックオーバーフローを回避できるという利点があります。状況に応じて最適な手法を選択してください。