C++で二分木のすべての右葉ノードの合計を求める3つの方法

問題概要

この記事では、C++ を使って二分木の中からすべての右葉ノード(親ノードの右側の子であり、かつ子ノードを持たないノード)を検出し、その値の合計を求める方法を解説します。

まず、具体例で問題を確認してみましょう。

入力:

出力: 8

説明:

この木の右葉ノードは 1 と 7
合計 = 1 + 7 = 8

上図の二分木では、ノード 4 の右の子である「1」と、ノード 6 の右の子である「7」が右葉ノードに該当します。したがって、合計は 1 + 7 = 8 となります。

解法1: 再帰によるアプローチ

最もシンプルな解決策は、木を根から葉へ向かって再帰的に走査する方法です。各ノードに対して、その右の子が葉ノードであるかどうかを判定し、右葉ノードであればその値を合計に加算します。木全体の走査が完了したら、合計値を返します。

サンプルプログラム

#include <iostream>
using namespace std;
struct Node{
    int key;
    struct Node* left, *right;
};
Node *newNode(int 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 findRightLeavesSum(Node *root){
    int sum = 0;
    if (root != NULL){
        if (isLeafNode(root->right))
            sum += root->right->key;
        else
            sum += findRightLeavesSum(root->right);
        sum += findRightLeavesSum(root->left);
    }
    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 right leaves of the tree is "<<findRightLeavesSum(root);
    return 0;
}

実行結果

The sum of right leaves of the tree is 8

解法2: スタックを使った反復処理(DFS)

次に、明示的なスタックを用いた深さ優先探索(DFS)による反復的なアプローチを紹介します。スタックからノードを取り出すたびに、その右の子が存在するかどうかを確認し、存在していてかつ葉ノードであれば、その値を合計に加算します。スタックが空になった時点で、合計を出力します。

サンプルプログラム

#include<bits/stdc++.h>
using namespace std;
struct Node{
    int key; struct Node* left, *right;
};
Node *newNode(int k){
    Node *node = new Node;
    node->key = k;
    node->right = node->left = NULL;
    return node;
}
int findRightLeavesSum(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->right != NULL){
            treeNodes.push(currentNode->right);
            if(currentNode->right->right == NULL &&
                currentNode->right->left == NULL){
                sum += currentNode->right->key ;
            }
        }
        if (currentNode->left != NULL)
            treeNodes.push(currentNode->left);
    }
    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 right leaves of the tree is "<<findRightLeavesSum(root);
    return 0;
}

実行結果

The sum of right leaves of the tree is 8

解法3: キューを使った幅優先探索(BFS)

3つ目のアプローチは、キューを用いた幅優先探索(BFS)です。キューには「ノードへのポインタ」と「そのノードが親の右側の子かどうかを示すフラグ」のペアを格納します。取り出したノードが葉であり、かつ右側の子である場合にのみ、その値を合計に加算します。走査が終了したら合計を出力します。

サンプルプログラム

#include<bits/stdc++.h>
using namespace std;
struct Node{
    int key; struct Node* left, *right;
};
Node *newNode(int k){
    Node *node = new Node;
    node->key = k;
    node->right = node->left = NULL;
    return node;
}
int findRightLeavesSum(Node* root) {
    if (root == NULL)
        return 0;
    queue<pair<Node*, bool> > treeNodes;
    treeNodes.push({ root, 0 });
    int sum = 0;
    while (!treeNodes.empty()) {
        Node* temp = treeNodes.front().first;
        bool is_right_child = treeNodes.front().second;
        treeNodes.pop();
        if (!temp->left && !temp->right && is_right_child)
            sum = sum + temp->key;
        if (temp->left) {
            treeNodes.push({ temp->left, 0 });
        }
        if (temp->right) {
            treeNodes.push({ temp->right, 1 });
        }
    }
    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 right leaves of the tree is "<<findRightLeavesSum(root);
    return 0;
}

実行結果

The sum of right leaves of the tree is 8

まとめ

本記事では、二分木における右葉ノードの合計を求める3つの手法(再帰・DFS・BFS)を紹介しました。いずれの方法も時間計算量は O(n)、空間計算量は O(n) となります。再帰版はコードが簡潔で読みやすい反面、木が非常に深い場合はスタックオーバーフローのリスクがあります。一方、反復版(DFS・BFS)は明示的なデータ構造を使用するため、そのようなリスクを回避できます。状況に応じて最適な手法を選択してください。