트리의 클론에서 이진 트리의 대응 노드 찾기

문제설명

두 개의 이진 트리가 주어지고 원래 트리의 노드에 대한 참조가 주어집니다
나무는 나무의 복사본입니다.
트리의 동일한 노드에 대한 참조를 반환합니다
두 트리 또는 노드 중 어느 것도 변경할 수 없으며 대답은 트리의 노드에 대한 참조 여야 합니다

예시 1:

입력: tree = [7,4,3,null,null,6,19], target = 3
출력: 3
설명: 모든 예에서는 원본 트리와 복제된 트리가 표시됩니다. 대상 노드는 원래 트리의 녹색 노드입니다. 대답은 복제된 트리의 노란색 노드입니다.

예시 2:

입력: 트리 = [7], 대상 = 7
출력: 7

예시 3:

입력: 트리 = [8,null,6,null,5,null,4,null,3,null,2,null,1], 대상 = 4 출력
: 4

제약 :

의 노드 수가 tree범위 내에 있습니다 .[1, 104]
노드의 값은 tree고유합니다.
targetnode는 트리의 노드이고 original가 아닙니다 null.

문제풀이

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

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

<내 코드의 흐름>

• val: 노드의 값입니다. 기본값은 0입니다.
• left: 왼쪽 자식 노드입니다. 기본값은 None입니다.
• right: 오른쪽 자식 노드입니다. 기본값은 None입니다.

1. 원본 트리의 노드가 None이면 None을 반환합니다.
2. 원본 트리의 노드가 타겟 노드와 동일하면 클론된 트리의 해당 노드를 반환합니다
3. 왼쪽 서브트리를 탐색합니다.
4. 왼쪽 서브트리에서 타겟을 찾으면 결과를 반환합니다.
5. 오른쪽 서브트리를 탐색합니다.