Kiểm tra tính chất Children Sum trong cây nhị phân trong C++

Kiểm tra cây nhị phân có thỏa mãn Children Sum Property: giá trị mỗi nút bằng tổng giá trị hai nút con (nút con null tính là 0).

Duyệt đệ quy: nếu nút và cả hai cây con thỏa mãn thì trả true.

Ví dụ

#include <iostream>
using namespace std;

class node {
public:
    int data;
    node* left;
    node* right;
};

bool isValidBinaryTree(node* nd) {
    int left_data = 0, right_data = 0;
    if(nd == NULL || (nd->left == NULL && nd->right == NULL))
        return 1;
    else{
        if(nd->left != NULL)
            left_data = nd->left->data;
        if(nd->right != NULL)
            right_data = nd->right->data;
        if((nd->data == left_data + right_data)&& isValidBinaryTree(nd->left) && isValidBinaryTree(nd->right))
            return true;
        else
            return false;
    }
}

node* getNode(int data) {
    node* newNode = new node();
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

int main() {
    node *root = getNode(10);
    root->left = getNode(8);
    root->right = getNode(2);
    root->left->left = getNode(3);
    root->left->right = getNode(5);
    root->right->right = getNode(2);
    if(isValidBinaryTree(root))
        cout << "The tree satisfies the children sum property ";
    else
        cout << "The tree does not satisfy the children sum property ";
}

Kết quả

The tree satisfies the children sum property