C++で二分木の右側の葉（右葉）の合計を求める方法

二分木が与えられたとき、その木に含まれるすべての「右葉（右側につながった葉ノード）」の値の合計を求める問題を考えてみましょう。

例えば、次のような二分木が入力として与えられた場合を考えます。

この場合の出力は 17 になります。この二分木には値が 7 と 10 の2つの右葉が存在するためです。

解決のためのアプローチ

この問題は、DFS（深さ優先探索）を利用することで効率的に解くことができます。手順は以下の通りです。

• dfs() 関数を定義します。引数としてノード（node）とブール値のフラグ（add）を受け取ります。
• node が null の場合は、何もせずに処理を終了して戻ります。
• node の左の子・右の子がどちらも存在しない（＝葉ノードである）、かつ add が true の場合、ret にそのノードの値を加算します。
• dfs(node->left, false) を呼び出します。左側の子孫は右葉にならないためです。
• dfs(node->right, true) を呼び出します。右側の子孫は右葉の候補になるためです。

メインとなる solve メソッドでは、以下の処理を行います。

• ret を 0 で初期化します。
• dfs(root, true) を呼び出します。
• 最後に ret を返します。

それでは、理解を深めるために実際の実装例を見てみましょう。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
class TreeNode{
    public:
    int val;
    TreeNode *left, *right;
    TreeNode(int data){
        val = data;
        left = NULL;
        right = NULL;
    }
};
class Solution {
    public:
    int ret = 0;
    void dfs(TreeNode* node, bool add){
        if(!node)
            return;
        if(!node->left && !node->right && add){
            ret += node->val;
        }
        dfs(node->left, false);
        dfs(node->right, true);
    }
    int solve(TreeNode* root) {
        ret = 0;
        dfs(root, true);
        return ret;
    }
};
int main(){
    Solution ob;
    TreeNode *root = new TreeNode(3);
    root->left = new TreeNode(9);
    root->right = new TreeNode(10);
    root->left->left = new TreeNode(15);
    root->left->right = new TreeNode(7);
    cout << (ob.solve(root));
    return 0;
}

入力

TreeNode *root = new TreeNode(3);
root->left = new TreeNode(9);
root->right = new TreeNode(10);
root->left->left = new TreeNode(15);
root->left->right = new TreeNode(7);

出力

17