C++で二分木がSumTree（総和木）かどうかを判定する方法

ここでは、与えられた二分木が「SumTree（総和木）」であるかどうかを判定する方法を解説します。まずは、SumTreeとはどのような木なのかを確認しておきましょう。

SumTreeとは

SumTreeとは、すべての内部ノードが「左の子と右の子の値の合計」を保持する特殊な二分木です。木の根（ルート）には、それより下位に存在する全要素の合計値が格納されます。なお、葉ノードのみからなる木や空の木も、定義上はSumTreeとみなされます。以下はSumTreeの一例です。

例えば上図の木では、根の値26が左部分木（10 + 4 + 6 = 20）と右部分木（3 + 3 = 6）の合計と一致しており、同様の関係がすべての内部ノードで成り立っています。

判定の考え方

判定には非常にシンプルなテクニックを使います。「左部分木の要素の合計」と「右部分木の要素の合計」を求め、その合計値が現在のノードの値と一致するかどうかを確認するというものです。一致していればその木はSumTreeであり、このチェックを再帰的にすべてのノードへ適用していきます。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
class node {
   public:
   int data;
   node* left, *right;
};
int sum_of_nodes(node *root) {
   if(root == NULL)
      return 0;
   return sum_of_nodes(root->left) + root->data + sum_of_nodes(root->right);
}
int isSumTree(node* node) {
   int left_sum, right_sum;
   if(node == NULL || (node->left == NULL && node->right == NULL))
      return 1;
   left_sum = sum_of_nodes(node->left);
   right_sum = sum_of_nodes(node->right);
   if((node->data == left_sum + right_sum) && isSumTree(node->left) && isSumTree(node->right))
      return 1;
   return 0;
}
node* getNode(int data) {
   node* newNode = new node();
   newNode->data = data;
   newNode->left = newNode->right = NULL;
   return newNode;
}
int main() {
   node *root = getNode(26);
   root->left = getNode(10);
   root->right = getNode(3);
   root->left->left = getNode(4);
   root->left->right = getNode(6);
   root->right->right = getNode(3);
   if(isSumTree(root))
      cout << "The tree is Sum Tree";
   else
      cout << "The tree is not a Sum Tree";
}

出力結果

The tree is Sum Tree

コードのポイント

• sum_of_nodes関数：指定されたノードを根とする部分木全体の値の合計を、再帰的に計算して返します。
• isSumTree関数：ノードがNULL、または葉ノードの場合は1（真）を返します。それ以外の場合は、左右の部分木の合計を求めて現在のノードの値と照合し、さらに左右の部分木それぞれに対しても再帰的にSumTree判定を行います。
• getNode関数：新しいノードを生成するための補助関数です。

計算量に関する注意点

上記の実装では、各ノードごとに部分木の合計をその都度計算し直しているため、最悪の場合の時間計算量はO(n²)になります。木の規模が大きくなる可能性がある場合は、後行順巡回（post-order traversal）を利用して「部分木の合計値」と「その部分木がSumTreeであるかどうか」を同時に返すよう実装することで、時間計算量をO(n)まで抑えることができます。