주어진 이진 트리가 C++에서 SumTree인지 확인하십시오.

여기서는 이진 트리가 합 트리인지 여부를 확인하는 방법을 살펴보겠습니다. 이제 문제는 sum-tree가 무엇이냐는 것입니다. 합계 트리는 노드가 자식의 합계 값을 보유하는 이진 트리입니다. 트리의 루트에는 그 아래에 있는 모든 요소의 전체 합계가 포함됩니다. 이것은 sum-tree의 예입니다 -

이를 확인하기 위해 우리는 간단한 트릭을 따를 것입니다. 합 값이 루트와 같으면 왼쪽 및 오른쪽 하위 트리 요소의 합을 찾고 그것이 합 트리입니다. 이것은 하나의 재귀적 접근 방식이 될 것입니다.

예

#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