Find Corresponding Node in Cloned Binary Tree ใน C++

ให้ **Binary Tree 2 ต้น**: original และ cloned (Clone ของ Original) และ Pointer target ชี้ไป Node ใน Original Tree หา **Pointer ไป Node เดียวกันใน Cloned Tree**

ตัวอย่าง

Tree:       7
           / \
          4   3  <- Target (Original)
             / \
            6  19

Cloned Tree โครงสร้างเหมือนกันทุกอย่าง
Target ใน Cloned: Node ที่มีค่า 3
Output: 3

แนวทาง: Simultaneous DFS (Parallel Traversal)

เดิน **พร้อมกัน** ทั้ง 2 ต้น ตรง Node ที่ตรงกัน:

1. ถ้า originalNode == nullptr -> Return NULL
2. ถ้า originalNode == target **AND** ค่าเท่ากัน (Double Check) -> Return clonedNode
3. Recurse Left: solve(orig->left, cloned->left, target)
4. Recurse Right: solve(orig->right, cloned->right, target)
5. Return Left Result ถ้ามี Else Right Result

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

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

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    TreeNode* solve(TreeNode* orig, TreeNode* cloned, TreeNode* target) {
        if (!orig) return NULL;
        if (orig == target && orig->val == cloned->val) return cloned; // Found!

        TreeNode* left = solve(orig->left, cloned->left, target);
        TreeNode* right = solve(orig->right, cloned->right, target);
        return left ? left : right;
    }

    TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target) {
        return solve(original, cloned, target);
    }
};

Input / Output

Input:  [7,4,3,null,null,6,19] target=3
Output: 3 (Pointer to node with value 3 in cloned tree)

ความซับซ้อน (Complexity)

• Time: O(N) — Visit ทุก Node สูงสุด 1 ครั้ง
• Space: O(H) — Recursion Stack (H = Height, Worst O(N))

หมายเหตุ

• ไม่ต้องเปรียบเทียบค่า (Value) เพราะอาจมี Duplicate Values -> ใช้ **Pointer Equality** (orig == target) เป็นหลัก
• โค้ดตัวอย่างเช็ค orig->val == cloned->val เพื่อ Safety (Clone ควรเหมือนกัน)
• Iterative BFS/DFS ก็ได้ (Queue/Stack Pair)

โจทย์ LeetCode 1379 ครับ