หา Mirror Node ใน Binary Tree ด้วย C++

ภาพรวมปัญหา

ได้รับ Binary Tree และโหนดเป้าหมาย หา Mirror Node (โหนดกระจก) ใน subtree ตรงข้าม

ตัวอย่าง

เอาต์พุต

Mirror of 2 is 6
Mirror of 5 not present

วิธีแก้ปัญหา

Recursive ด้วย 2 pointers เดินพร้อมกันใน Left และ Right Subtree

• left pointer เดิน Left→Left, Right→Right
• right pointer เดิน Right→Right, Left→Left (Mirror)
• เจอ target ใน left → คืนค่า right, และกลับกัน

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

#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 findMirrorNodeBT(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 = findMirrorNodeBT(root, target);
    cout << "Mirror of " << target << " is " << (mirror ? to_string(mirror) : "not present") << endl;
    
    target = root->left->left->right->key;  // 5
    mirror = findMirrorNodeBT(root, target);
    cout << "Mirror of " << target << " is " << (mirror ? to_string(mirror) : "not present") << endl;
    return 0;
}

เอาต์พุต

Mirror of 2 is 6
Mirror of 5 is not present

สรุป

Recursive symmetric traversal หา mirror ใน O(N) เวลา O(H) พื้นที่ (stack)