문제를 이해하고 있다면 바로 풀이를 보면 됨
전체 코드로 바로 넘어가도 됨
마음대로 번역해서 오역이 있을 수 있음

Problem

두 개의 이진 트리 original과 cloned가 주어지고, original 트리에 노드 target을 참조한다.
cloned 트리는 original 트리의 복사본이다.
cloned 트리에서 같은 노드를 참조한 것을 반환해라.

Example

#1

Input: tree = [7, 4, 3, null, null, 6, 19], target = 3
Output: 3
Explanation: 모든 예에서 original 트리와 cloned 트리를 보여준다. target 노드는 original 트리에서 초록 node이다. 답은 cloned 트리에서 노란 node이다.

#2

Input: tree = [7], target = 7
Output: 7

#3
Input: tree = [8, null, 6, null, 5, null, 4, null, 3, null, 2, null, 1], target = 4
Output: 4

Constraints

• tree에서 노드의 수는 [1, 10^4]이다.
• tree의 노드의 값은 고유하다.
• target 노드는 original 트리의 노드이고 null이 아니다.

Solved

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

class Solution {
    public final TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target) {
        if(original == null){
            return null;
        }

        if(original == target){
            return cloned;
        }

        TreeNode left = getTargetCopy(original.left, cloned.left, target);

        if(left != null){
            return left;
        }

        return getTargetCopy(original.right, cloned.right, target);
    }
}