99클럽 코테 스터디 3일차 TIL + 이진 검색 트리(2)

 

오늘의 공부 키워드

• 이진검색 트리(BST) 새로운 문제
• Leetcode 1379 Find a Corresponding Node a Binary Tree in a Clone of That Tree

 

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

 

문제 설명

이 문제는 두 개의 이진 트리(original과 cloned)가 주어졌을 때, original 트리의 특정 노드(target 노드)에 대응하는 cloned 트리의 노드를 찾아 그 노드에 대한 참조를 반환하는 것입니다. 주어진 조건에 따라 트리의 구조와 노드의 값이 유일하다는 점을 고려해야 합니다.

 

입력

• 두 개의 이진 트리 (original과 cloned)
• original 트리의 특정 노드(target)

출력

• cloned 트리에서 original 트리의 target 노드와 동일한 위치에 있는 노드의 참조를 반환

예제

1. 예제 1:
   • 입력: tree = [7,4,3,null,null,6,19], target = 3
   • 출력: 3
   • 설명: original 트리에서 값이 3인 노드가 target 노드입니다. cloned 트리에서도 동일한 위치에 있는 노드가 반환됩니다.
2. 예제 2:
   • 입력: tree = [7], target = 7
   • 출력: 7
   • 설명: 트리가 하나의 노드만 가지고 있으므로, target 노드는 7입니다. cloned 트리에서도 동일한 노드를 반환합니다.
3. 예제 3:
   • 입력: tree = [8,null,6,null,5,null,4,null,3,null,2,null,1], target = 4
   • 출력: 4
   • 설명: original 트리에서 값이 4인 노드가 target 노드입니다. cloned 트리에서도 동일한 위치에 있는 노드가 반환됩니다.

제약 조건

• 트리의 노드 수는 1 이상 10^4 이하입니다.
• 트리의 노드 값은 유일합니다.
• target 노드는 original 트리의 노드 중 하나이며 null이 아닙니다.

 

해결 방법

이 문제를 해결하기 위해 DFS(깊이 우선 탐색)나 BFS(너비 우선 탐색)를 사용하여 트리를 순회할 수 있습니다. 두 트리를 동시에 순회하면서 original 트리에서 target 노드를 찾을 때, 동일한 위치의 cloned 트리 노드를 반환합니다.

 

코드

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def getTargetCopy(original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
    if original is None:
        return None
    if original == target:
        return cloned
    left = getTargetCopy(original.left, cloned.left, target)
    if left is not None:
        return left
    return getTargetCopy(original.right, cloned.right, target)

 

코드 설명

1. original 노드와 cloned 노드를 동시에 탐색합니다.
2. original 노드가 target 노드와 같은 경우, cloned 노드를 반환합니다.
3. 왼쪽 서브트리를 먼저 탐색하고, 왼쪽에서 찾지 못하면 오른쪽 서브트리를 탐색합니다.

즉, 이 코드는 target 노드와 동일한 위치에 있는 cloned 트리의 노드를 반환합니다. 이로 인해 출력이 3이 되는 것입니다.

 

오늘의 회고

• 이진 검색 트리를 다르게 푸는 방법을 알수 있어서 좋았다.
• 여전히 개념에 대한 이해가 안되어 코드 리뷰 수준으로 문제를 푼점은 다시한번 아쉽게 된다.
• 그래도 이렇게 기록으로 남기는건 나중에 다시한번 풀어보고 어떻게 풀었는지 알기 위해서 기록을 남긴다.
• LV1의 문제라지만 바로바로 문제를 풀지 못하는점은 아직도 아쉽다.
• CODE UP 기초 문제도 순항중인데 다양한 인사이트를 얻고 있다.
• 좀더 파이썬에 대해서 공부를 해야할거같다.