C++で二分木の子ノード合計プロパティを検証する方法

二分木が与えられたとき、次のプロパティ(性質)を満たしていれば、その二分木は有効とみなされます。

• 各ノードのデータ値は、左の子ノードと右の子ノードの値の合計と一致していなければなりません。どちらかの側に子ノードが存在しない場合は、その値は0として扱われます。

例えば、以下のような木が与えられた場合、このプロパティを満たしていることになります。

この性質を確認するための特別なトリックは存在せず、木を再帰的に走査する必要があります。ノードとその両方の子がプロパティを満たしていればtrueを返し、そうでなければfalseを返します。

アルゴリズムの流れ

検証は以下の手順で行われます。

1. ノードがNULL、または葉ノード(子を持たないノード)であれば、trueを返します。
2. 左の子が存在すればその値を取得し、存在しなければ0とします。
3. 右の子についても同様に処理します。
4. 現在のノードの値が左右の子の値の合計と一致し、かつ左右の部分木も再帰的にプロパティを満たしていればtrueを返します。

実装例

#include <iostream>
using namespace std;
class node {
   public:
   int data;
   node* left;
   node* right;
};
bool isValidBinaryTree(node* nd) {
   int left_data = 0, right_data = 0;
   if(nd == NULL || (nd->left == NULL && nd->right == NULL))
      return 1;
   else{
      if(nd->left != NULL)
         left_data = nd->left->data;
      if(nd->right != NULL)
         right_data = nd->right->data;
      if((nd->data == left_data + right_data)&& isValidBinaryTree(nd->left) && isValidBinaryTree(nd->right))
         return true;
      else
         return false;
   }
}
node* getNode(int data) {
   node* newNode = new node();
   newNode->data = data;
   newNode->left = NULL;
   newNode->right = NULL;
   return newNode;
}
int main() {
   node *root = getNode(10);
   root->left = getNode(8);
   root->right = getNode(2);
   root->left->left = getNode(3);
   root->left->right = getNode(5);
   root->right->right = getNode(2);
   if(isValidBinaryTree(root))
      cout << "The tree satisfies the children sum property ";
   else
      cout << "The tree does not satisfy the children sum property ";
}

出力

The tree satisfies the children sum property

計算量について

このアルゴリズムの時間計算量はO(n)です(nは木のノード数)。すべてのノードを一度だけ訪問するため、効率的に検証できます。また、再帰呼び出しの深さは木の高さに依存するため、バランスの取れていない木ではスタック領域に注意が必要です。