1. 오늘의 문제

Find a Corresponding Node of a Binary Tree in a Clone of That Tree

• 출처 : leetcode

2. 문제 분석

• 이진트리 : original
• 이진트리 original의 복사본 : cloned
• target : original의 특정 노드의 주소값
• 리턴 값 : original의 특정 노드에 해당하는 cloned 노드의 주소값
• tree 노드의 개수 : 1부터 $10^4$ 까지

3. 입출력 예시

• Input : tree = [7, 4, 3, null, null, 6, 19], target = 3
• Output : 3
  
  
• Input : tree = [7], target =7
• Output : 7
  
  
• Input : tree = [8, null, 6, null, 5, unll, 4, null, 3, null, 2, null, 1], target =4
• Output : 4

4. 문제 풀이

1. 왼쪽 오른쪽 탐색 하면 될 듯
2. root 노드가 null이면 null 리턴
3. root 노드와 target 비교
4. root 노드의 왼쪽 서브 트리 탐색
5. root 노드의 오른쪽 서브 트리 탐색

5. 구현 코드

/**
 * 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) {
        // Base Case : 원본 트리의 노드가 null인 경
        if (original == null) {
            return null;
        }

        // 찾으면 그 주소값 리턴
        if (original == target) {
            return cloned;
        }

        // 왼쪽 서브트리 순회
        TreeNode leftTree = getTargetCopy(original.left, cloned.left, target);
        if (leftTree != null) {
            return leftTree;
        }

        // 오른쪽 서브트리 순회
        return getTargetCopy(original.right, cloned.right, target);
    }
}

6. 오늘의 회고

• 뭔가 오늘 문제가 잘 이해가 안되서.. 일단 문제 요청에 충실한 풀이를 했다.
• 여전히 재귀 호출 탐색은 머리가 아프다..
  

#99클럽 #코딩테스트 준비 #개발자 취업 #항해99 #TIL