XOR đường đi giữa hai nút trong cây nhị phân C++

Trong bài toán này, cho một cây nhị phân và hai nút của cây. Nhiệm vụ là in ra XOR của tất cả các nút trên đường đi giữa hai nút đó.

Ví dụ:

Cần tìm XOR giữa nút 2 và 3.

Đường đi từ 2 đến 3: 2 → 6 → 1 → 3.

XOR = 2 ^ 6 ^ 1 ^ 3.

Output – 7

Để giải, ta tìm đường đi từ gốc đến hai nút. Khi duyệt từ gốc, có hai trường hợp: hai nút nằm cùng phía hoặc hai phía khác nhau của gốc. Nếu cùng phía, các nút không trên đường đi sẽ được duyệt hai lần và triệt tiêu. Nếu khác phía, toàn bộ đường từ gốc đến nút cần xét. Mỗi bước tính XOR với kết quả trước, tiết kiệm không gian.

Ví dụ minh họa

#include <bits/stdc++.h>
using namespace std;

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

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

void pathStoD(Node* root, unordered_map<int, int>& path, int XOR) {
    if (!root)
        return;
    path.insert(make_pair(root->data, XOR ^ root->data));
    XOR ^= root->data;
    if (root->left)
        pathStoD(root->left, path, XOR);
    if (root->right)
        pathStoD(root->right, path, XOR);
}

int findPathXOR(unordered_map<int, int> path, int node1, int node2) {
    return path[node1] ^ path[node2];
}

int main() {
    struct Node* root = getNode(1);
    root->left = getNode(6);
    root->left->left = getNode(2);
    root->left->right = getNode(4);
    root->right = getNode(3);
    root->right->left = getNode(7);
    root->right->right = getNode(5);
    
    int XOR = 0;
    unordered_map<int, int> mp;
    int source = 2;
    int destination = 3;
    
    pathStoD(root, mp, XOR);
    
    cout << "XOR của tất cả nút từ " << source << " đến " << destination << " của cây là: ";
    cout << findPathXOR(mp, source, destination);
    
    return 0;
}

Kết quả

XOR của tất cả nút từ 2 đến 3 của cây là: 7