해당 트리의 복제본에서 이진 트리의 해당 노드 찾기

두 개의 이진 트리original 및 cloned가 주어지고 원래 트리의 노드target에 대한 참조가 주어집니다.
cloned 트리는 original 트리의 복사본입니다.
cloned 트리에서 동일한 노드에 대한 참조를 반환합니다.

두 개의 트리 또는 target 노드를 변경할 수 없으며 응답은 cloned 트리의 노드에 대한 참조여야 합니다.

예 1:



입력: 트리 = [7,4,3,null,null,6,19], 대상 = 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의 노드 값이 고유합니다.

target 노드는 original 트리의 노드이며 null가 아닙니다.

후속 조치: 트리에서 반복되는 값이 허용되면 문제를 해결할 수 있습니까?

해결책:

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

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if not p or not q:
            if p or q:
                return False
            return True
        if p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right):
            return True

    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
        nodes = [(original, cloned)]
        while len(nodes) > 0:
            og, cl = nodes.pop()
            if self.isSameTree(og, target):
                return cl
            if og and cl:
                nodes.append((og.left, cl.left))
                nodes.append((og.right, cl.right))
        return None