Count Adjacent Nodes with Odd XOR in Binary Tree: นับคู่โหนดติดกันที่ XOR เป็นเลขคี่ใน C++

ปัญหา

กำหนด Binary Tree หาจำนวนคู่ โหนด Parent-Child ที่ติดกัน ที่ parent.val XOR child.val เป็น เลขคี่

ตัวอย่าง: Tree ด้านล่าง → 5 คู่

ข้อสังเกต: XOR Properties

a XOR b เป็นเลขคี่ ⟺ LSB (Least Significant Bit) ต่างกัน

• คี่ (LSB=1) XOR คู่ (LSB=0) = คี่
• คี่ XOR คี่ = คู่
• คู่ XOR คู่ = คู่

→ นับคู่ Parent-Child ที่ Parity ต่างกัน (หนึ่งคู่ หนึ่งคี่)

โค้ด C++

#include <iostream>
using namespace std;

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

int countPairs(Node* root, Node* parent = nullptr) {
    if (!root) return 0;
    
    int res = 0;
    if (parent && ((parent->data ^ root->data) % 2 != 0)) {
        res++;  // XOR เป็นคี่
    }
    
    return res + countPairs(root->left, root) + countPairs(root->right, root);
}

Node* newNode(int data) {
    Node* temp = new Node;
    temp->data = data;
    temp->left = temp->right = nullptr;
    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 << countPairs(root) << endl;  // 5
    return 0;
}

Tree Structure & Verification

        15 (odd)
       /  \
   13(o)  18(e)
   / \    /  \
 12(e)14(e)17(o)21(o)

รวม 5 คู่

ความซับซ้อน

• Time: O(n) - เยี่ยมทุกโหนด 1 ครั้ง
• Space: O(h) - Recursion stack (h = ความสูงต้นไม้)

Input / Output

Input:  Tree as above
Output: 5