C++のバイナリツリーで子の合計プロパティを確認します

二分木があるとします。二分木は、次の特性を満たす場合に有効です。

• 各ノードには、左右の子の値の合計と同じデータ値が含まれている必要があります。いずれかの側に子がない場合は、0として扱われます。

以下のように、指定されたプロパティを満たすツリーが存在するとします。

これをチェックするそのようなトリックはありません。ノードとその子の両方がプロパティを満たしている場合はツリーを再帰的にトラバースする必要があり、それ以外の場合はfalseを返します。

例

#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