ตรวจสอบว่า Binary Tree ที่ระบุคือ SumTree ใน C++ . หรือไม่

ที่นี่เราจะดูวิธีการตรวจสอบว่าไบนารีทรีเป็น 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