Đếm cặp nút liền kề có XOR lẻ trong cây nhị phân C++

Trong hướng dẫn này, ta sẽ thảo luận chương trình để tìm số lượng cặp nút liền kề có XOR là số lẻ trong cây nhị phân.

Cho một cây nhị phân. Nhiệm vụ là đếm số cặp nút cha-con có XOR là số lẻ.

Ví dụ

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node *left, *right;
};

int count_pair(Node* root, Node* parent = NULL) {
    if(root == NULL) return 0;
    int res = 0;
    if(parent != NULL && ((parent->data ^ root->data) % 2))
        res++;
    return res + count_pair(root->left, root) + count_pair(root->right, root);
}

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

int main() {
    Node* root = newNode(15);
    root->left = newNode(13);
    root->left->left = newNode(12);
    root->left->right = newNode(14);
    root->right = newNode(18);
    root->right->left = newNode(17);
    root->right->right = newNode(21);
    cout << count_pair(root);
    return 0;
}

Kết quả

5