ตรวจสอบ Children Sum Property ใน Binary Tree ใน C++

สมมติมี Binary Tree Tree ถูกต้องเมื่อตรงตาม Property: แต่ละ Node ต้องมีค่าเท่ากับผลรวมของ Left และ Right Children ถ้าไม่มีลูกด้านไหน ให้ถือเป็น 0

ตัวอย่าง Tree ที่ตรงตาม Property:

ไม่มีทริคพิเศษ ต้อง Traverse แบบ Recursive ถ้า Node และ Children ทั้งคู่ตรง Property คืนค่า true มิฉะนั้น false

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

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

ผลลัพธ์

The tree satisfies the children sum property