ตรวจสอบว่า Binary Tree เป็น SumTree หรือไม่ใน C++

ในบทความนี้เราจะมาดูวิธีการตรวจสอบว่า Binary Tree ที่กำหนดเป็น SumTree หรือไม่ SumTree คือ Binary Tree ที่โหนดแต่ละตัวมีค่าเท่ากับผลรวมของลูกทั้งสองฝั่ง รากของ Tree จะมีค่าเท่ากับผลรวมของทุกโหนดที่อยู่ด้านล่าง ตัวอย่าง SumTree ดังภาพ:

ในการตรวจสอบ เราจะใช้วิธีง่ายๆ คือหาผลรวมของโหนดใน Left Subtree และ Right Subtree หากผลรวมเท่ากับค่าของ Root แล้วก็เป็น SumTree วิธีนี้ใช้แนวคิด Recursive

ตัวอย่างโค้ด C++

#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