Tìm nút đối xứng của nút cho trước trong cây nhị phân C++

Giới thiệu

Cho cây nhị phân. Tìm nút đối xứng (mirror) của một nút cho trước: nút ở vị trí đối xứng qua gốc trong cây con đối diện.

Ví dụ minh họa

Mirror của B là E.

Phương pháp giải: Đệ quy hai con trỏ

Từ gốc, dùng hai con trỏ đi song song: trái của cây trái với phải của cây phải, và phải của cây trái với trái của cây phải. Khi tìm thấy khóa ở một bên, trả về nút bên kia.

Chương trình minh họa

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

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

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

int mirrorNodeRecur(int target, Node* left, Node* right) {
    if (!left || !right) return 0;
    if (left->key == target) return right->key;
    if (right->key == target) return left->key;
    
    int mirror = mirrorNodeRecur(target, left->left, right->right);
    if (mirror) return mirror;
    return mirrorNodeRecur(target, left->right, right->left);
}

int findMirrorNode(Node* root, int target) {
    if (!root) return 0;
    if (root->key == target) return target;
    return mirrorNodeRecur(target, root->left, root->right);
}

int main() {
    Node* root = newNode(1);
    root->left = newNode(2);
    root->left->left = newNode(3);
    root->left->left->left = newNode(4);
    root->left->left->right = newNode(5);
    root->right = newNode(6);
    root->right->left = newNode(7);
    root->right->right = newNode(8);
    
    int target = root->left->key; // 2
    int mirror = findMirrorNode(root, target);
    cout << "Node: " << target << endl;
    if (mirror) cout << "Mirror: " << mirror;
    else cout << "No mirror!";
    
    target = root->left->left->right->key; // 5
    mirror = findMirrorNode(root, target);
    cout << "\n\nNode: " << target << endl;
    if (mirror) cout << "Mirror: " << mirror;
    else cout << "No mirror!";
    return 0;
}

Đầu ra

Node: 2
Mirror: 6

Node: 5
No mirror!