Kiểm tra cây nhị phân có phải là SumTree trong C++

Chúng ta sẽ xem cách kiểm tra một cây nhị phân có phải là SumTree hay không. SumTree là cây nhị phân mà giá trị của mỗi nút bằng tổng giá trị của hai nút con của nó. Nút gốc sẽ chứa tổng của tất cả các nút trong cây. Dưới đây là ví dụ một SumTree:

Để kiểm tra, ta dùng đệ quy: tính tổng các nút của cây con trái và cây con phải, nếu tổng bằng giá trị nút hiện tại và cả hai cây con cũng là SumTree thì cây hiện tại là SumTree.

Ví dụ

#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";
}

Kết quả

The tree is Sum Tree