99클럽 코테 스터디 2일차 TIL 1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree

 

 

 

https://leetcode.com/problems/find-a-corresponding-node-of-a-binary-tree-in-a-clone-of-that-tree/description/

주어진 두 이진 트리 original과 cloned가 있고, original 트리의 특정 노드 target이 주어집니다. cloned 트리는 original 트리의 복사본입니다. cloned 트리에서 동일한 노드를 참조로 반환하세요.

두 트리나 target 노드를 변경해서는 안 되며, 반환 값은 cloned 트리의 노드에 대한 참조여야 합니다.

예제 1:

입력: tree = [7, 4, 3, null, null, 6, 19], target = 3 출력: 3 설명: 모든 예제에서 original과 cloned 트리가 보여집니다. target 노드는 original 트리에서 녹색 노드입니다. 정답은 cloned 트리에서 노란색 노드입니다.

예제 2:

입력: tree = [7], target = 7 출력: 7

예제 3:

입력: tree = [8, null, 6, null, 5, null, 4, null, 3, null, 2, null, 1], target = 4 출력: 4

제약 조건:

• 트리의 노드 수는 [1, 10^4] 범위 내에 있습니다.
• 노드의 값은 고유합니다.
• target 노드는 original 트리의 노드이며 null이 아닙니다.

 

 

풀이

 

DFS를 이용하여 original 트리의 target 노드를 찾고, cloned 트리에서 동일한 위치의 노드를 반환하는 방식으로 구현

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
        def dfs(o: TreeNode, c: TreeNode) -> TreeNode:
            if o:
                # original 트리에서 target 노드를 찾으면 cloned 트리의 현재 노드를 반환
                if o == target:
                    return c
                # 왼쪽 자식을 탐색
                left = dfs(o.left, c.left)
                if left:
                    return left
                # 오른쪽 자식을 탐색
                return dfs(o.right, c.right)
            return None

        return dfs(original, cloned)

 

1. Solution 클래스:
   • getTargetCopy 메서드는 original, cloned, target 트리를 인수로 받아 target 노드와 동일한 노드를 cloned 트리에서 찾아 반환
   • 내부에 dfs 함수를 깊이 우선 탐색을 사용하여 original 트리에서 target 노드를 찾고, 해당 위치의 cloned 트리 노드를 반환
2. dfs 함수:
   • original 트리의 노드 o와 cloned 트리의 노드 c를 동시에 탐색
   • o가 target이면 c를 반환
   • left 변수에 왼쪽 자식을 재귀적으로 탐색한 결과를 저장하고, 결과가 있으면 반환
   • 오른쪽 자식을 재귀적으로 탐색하여 결과를 반환

결론

 

dfs 함수는 original과 cloned 트리를 동시에 탐색하면서 target 노드를 찾고, 그에 해당하는 cloned 트리의 노드를 반환