C++의 이진 트리에서 자식 합계 속성 확인

이진 트리가 있다고 가정합니다. 이진 트리는 다음 속성을 충족할 때 유효합니다.

• 각 노드는 왼쪽과 오른쪽 자식 값의 합과 같은 데이터 값을 포함해야 합니다. 어느 쪽에도 어린이가 없으면 0으로 처리됩니다.

주어진 속성을 만족하는 트리가 아래와 같이 있다고 가정합니다.

이를 확인할 수 있는 트릭은 없습니다. 노드와 해당 자식 모두가 속성을 만족하면 true를 반환하고 그렇지 않으면 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