特定のバイナリツリーがC++のSumTreeであるかどうかを確認します

ここでは、二分木が和木であるかどうかを確認する方法を説明します。ここで問題となるのは、合計ツリーとは何かです。合計ツリーは、ノードがその子の合計値を保持する二分木です。ツリーのルートには、その下にあるすべての要素の合計が含まれます。これは合計ツリーの例です-

これを確認するために、簡単なトリックに従います。合計値がルートと同じである場合は、左右のサブツリー要素の合計を見つけます。これが合計ツリーです。これは再帰的なアプローチの1つになります。

例

#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