C++で二分木における単一値の部分木を数える方法

二分木が与えられたとき、その木に含まれる「単一値の部分木（Single Valued Subtree）」の個数を求めるのが本記事の目的です。単一値の部分木とは、その部分木を構成するすべてのノードが同じ値を持つような部分木のことを指します。

問題の例

例として、次のような二分木を考えてみましょう。

この木には、以下に示す4つの単一値の部分木が存在します。

解法のアプローチ：ボトムアップ方式

この問題は、ボトムアップ（下から上へ）の再帰的なアプローチで効率的に解くことができます。基本的な考え方は次のとおりです。

• 各ノードを訪問する際、そのノードを根とする部分木が単一値であるかどうかを判定し、単一値であればカウンタを1増やします。
• 再帰呼び出しの結果として真偽値を返し、その戻り値を使って左右の子部分木が単一値かどうかを判断します。
• カウント用の変数は、参照渡し（リファレンスパラメータ）として再帰関数に渡すことで、再帰全体で共有できるようにします。

判定条件

あるノードを根とする部分木が単一値であるためには、次の条件をすべて満たす必要があります。

1. 左の子部分木が単一値である（存在しない場合は常に真）。
2. 右の子部分木が単一値である（存在しない場合は常に真）。
3. 左の子が存在する場合、その値が現在のノードの値と一致している。
4. 右の子が存在する場合、その値が現在のノードの値と一致している。

C++による実装例

#include <iostream>
using namespace std;
class Node {
   public:
      int data;
      Node* left, *right;
};
Node* getNode(int data) {
   Node* newNode = new Node;
   newNode->data = data;
   newNode->left = newNode->right = NULL;
   return newNode;
}
bool countSingleValuedSubtree(Node* root, int &count) {
   if (root == NULL)
   return true;
   bool left = countSingleValuedSubtree(root->left, count);
   bool right = countSingleValuedSubtree(root->right, count);
   if (left == false || right == false)
      return false;
   if (root->left && root->data != root->left->data)
      return false;
   if (root->right && root->data != root->right->data)
      return false;
      count++;
   return true;
}
int countSingleValSubtree(Node* root) {
   int count = 0;
   countSingleValuedSubtree(root, count);
   return count;
}
int main() {
   Node* root = getNode(5);
   root->left = getNode(1);
   root->right = getNode(5);
   root->left->left = getNode(5);
   root->left->right = getNode(5);
   root->right->right = getNode(5);
   cout << "Count of Single Valued Subtrees is: " << countSingleValSubtree(root);
}

実行結果

Count of Single Valued Subtrees is: 4

計算量について

このアルゴリズムは木の各ノードを一度だけ訪問するため、時間計算量は O(n) となります。ここで n は木のノード総数です。また、再帰呼び出しによるスタック領域を使用するため、空間計算量は木の高さに依存し、最悪の場合（木が線形に偏っている場合）は O(n)、バランスの取れた木の場合は O(log n) となります。