# 1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree

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

## DFS

# 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:
if not original or not cloned:
return None
if original == target: return cloned
left = self.getTargetCopy(original.left, cloned.left, target)
if left: return left
right = self.getTargetCopy(original.right, cloned.right, target)
return right


## BFS

# 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:
queue = deque([(original, cloned)])

while queue:
ori, clo = queue.popleft()
if ori == target:
return clo
if ori.left:
queue.append((ori.left, clo.left))
if ori.right:
queue.append((ori.right, clo.right))