Given two binary trees original and cloned and given a reference to a node target in the original tree.
The cloned tree is a copy of the original tree.
Return a reference to the same node in the cloned tree.
Note that you are not allowed to change any of the two trees or the target node and the answer must be a reference to a node in the cloned tree.
Follow up: Solve the problem if repeated values on the tree are allowed.
 
Example 1:

Input: tree = [7,4,3,null,null,6,19], target = 3
Output: 3
Explanation: In all examples the original and cloned trees are shown. The target node is a green node from the original tree. The answer is the yellow node from the cloned tree.

Example 2:

Input: tree = [7], target =  7
Output: 7

Example 3:

Input: tree = [8,null,6,null,5,null,4,null,3,null,2,null,1], target = 4
Output: 4

Example 4:

Input: tree = [1,2,3,4,5,6,7,8,9,10], target = 5
Output: 5

Example 5:

Input: tree = [1,2,null,3], target = 2
Output: 2

 
Constraints:

The number of nodes in the tree is in the range [1, 10^4].
The values of the nodes of the tree are unique.
target node is a node from the original tree and is not null.

Difficulty: MEDIUM
Tags: Tree algorithms

Graph traversal

Starter code:
# 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:
        

Solutions:
class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:

		def getnode(root):
			if not root:
				return None
			elif root.val == target.val:
				return root
			else:
				return getnode(root.left) or getnode(root.right)
		return getnode(cloned)


class Solution:

	def getTargetCopy(self, r1: TreeNode, r2: TreeNode, target: TreeNode) -> TreeNode:
		self.ans = 0
		self.flag = False

		def inorder(node, node2):
			if self.flag:
				return
			if not node:
				return node
			if node.val == target.val:
				self.ans = node2
				self.flag = True
				return node2
			inorder(node.left, node2.left)
			inorder(node.right, node2.right)
		inorder(r1, r2)
		return self.ans


class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
		stack = []
		while stack or cloned:
			while cloned:
				stack.append(cloned)
				cloned = cloned.left
			cloned = stack.pop()
			if cloned.val == target.val:
				return cloned
			cloned = cloned.right
		return None


class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
		return self.search(cloned, target)

	def search(self, head, target):
		if head is None:
			return None
		if head.val == target.val:
			return head
		else:
			left_node = self.search(head.left, target)
			if left_node is None:
				return self.search(head.right, target)
			else:
				return left_node


class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
		stack = []
		stackCloned = []
		while stack or original.left or original.right:
			while original:
				if original is target:
					return cloned
				if original.right:
					stack.append(original.right)
					stackCloned.append(cloned.right)
				original = original.left
				cloned = cloned.left
			original = stack.pop()
			cloned = stackCloned.pop()
		if original is target:
			return cloned


class Solution:

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


import queue

class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:

		def addToQueue(o_node, c_node, q, q_c):
			if o_node.val == target.val:
				return c_node
			q.put(o_node)
			q_c.put(c_node)
			return None
		if original is None or original.val == cloned.val == target.val:
			return cloned
		q = queue.Queue()
		q_c = queue.Queue()
		q.put(original)
		q_c.put(cloned)
		while not q.empty():
			o_node = q.get()
			c_node = q_c.get()
			if o_node.left and addToQueue(o_node.left, c_node.left, q, q_c):
				return c_node.left
			if o_node.right and addToQueue(o_node.right, c_node.right, q, q_c):
				return c_node.right
		return None


class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
		if cloned.val == target.val:
			return cloned
		if cloned.left:
			node = self.getTargetCopy(original, cloned.left, target)
			if node:
				return node
		if cloned.right:
			node = self.getTargetCopy(original, cloned.right, target)
			if node:
				return node
		return None


def first(gen):
	for elem in gen:
		return elem

def walk(original, cloned, target):
	if not original:
		return
	elif original is target:
		yield cloned
	else:
		yield from walk(original.left, cloned.left, target)
		yield from walk(original.right, cloned.right, target)

class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
		return first(walk(original, cloned, target))


class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
		return self.traverse(original, cloned, target)

	def traverse(self, root: TreeNode, cloned: TreeNode, target: TreeNode):
		if root is None:
			return None
		elif root == target:
			return cloned
		left = self.traverse(root.left, cloned.left, target)
		if left:
			return left
		right = self.traverse(root.right, cloned.right, target)
		if right:
			return right


class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
		if original == target:
			return cloned
		originalStack = []
		originalStack.append(original.right)
		originalStack.append(original.left)
		cloneStack = []
		cloneStack.append(cloned.right)
		cloneStack.append(cloned.left)
		while originalStack:
			currentCloneNode = cloneStack.pop()
			currentOriginalNode = originalStack.pop()
			if currentOriginalNode == target:
				return currentCloneNode
			if currentOriginalNode is not None:
				if currentOriginalNode.right:
					originalStack.append(currentOriginalNode.right)
					cloneStack.append(currentCloneNode.right)
				if currentOriginalNode.left:
					originalStack.append(currentOriginalNode.left)
					cloneStack.append(currentCloneNode.left)


class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
		path = []

		def traverse(x):
			if not x:
				return False
			if x is target:
				return True
			if traverse(x.left):
				path.append(True)
				return True
			if traverse(x.right):
				path.append(False)
				return True
			return False
		traverse(original)
		pointer = cloned
		for x in reversed(path):
			if x:
				pointer = pointer.left
			else:
				pointer = pointer.right
		return pointer


class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:

		def wtf(root, target):
			if root.val == target.val:
				print('a')
				return root
			if root.left:
				print('b')
				ans = wtf(root.left, target)
				if ans != None:
					return ans
			if root.right:
				print('c')
				ans = wtf(root.right, target)
				if ans != None:
					return ans
			return
		return wtf(cloned, target)


class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:

		def findNode(root):
			if root.val == target.val:
				return root
			else:
				if root.left is None and root.right is None:
					return None
				if root.left is not None:
					left = findNode(root.left)
					if left is not None:
						return left
				if root.right is not None:
					right = findNode(root.right)
					if right is not None:
						return right
		return findNode(cloned)


class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
		queue = [original]
		cloned_q = [cloned]
		while True:
			curr = queue.pop(0)
			cloned_curr = cloned_q.pop(0)
			if curr == target:
				return cloned_curr
			if curr.left:
				queue.append(curr.left)
				cloned_q.append(cloned_curr.left)
			if curr.right:
				queue.append(curr.right)
				cloned_q.append(cloned_curr.right)


from collections import deque

class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
		q = deque()
		q.append(cloned)
		while len(q):
			current = q.popleft()
			if current.val == target.val:
				return current
			q.extend([child for child in [current.left, current.right] if child is not None])


class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
		if not original or not cloned:
			return None
		S = [original]
		_S = [cloned]
		while len(S) > 0:
			curr = S.pop()
			_curr = _S.pop()
			if curr == target:
				return _curr
			if curr.left:
				S.append(curr.left)
				_S.append(_curr.left)
			if curr.right:
				S.append(curr.right)
				_S.append(_curr.right)
		return None


class Solution:

	def __init__(self):
		self.node = None

	def findtarget(self, org, clone, target):
		if not org or not clone:
			return None
		if org.val == target.val == clone.val:
			return clone
		return self.findtarget(org.left, clone.left, target) or self.findtarget(org.right, clone.right, target)

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
		return self.findtarget(original, cloned, target)


from collections import deque

class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
		self.ans = None
		self.num = target.val
		self.dfs(cloned)
		return self.ans

	def dfs(self, curr):
		if curr is None:
			return
		if curr.val == self.num:
			self.ans = curr
			return
		self.dfs(curr.left)
		self.dfs(curr.right)


def targetcopy(original, cloned, target):
	if original is None:
		return
	if original == target:
		return cloned
	x = targetcopy(original.left, cloned.left, target)
	if x:
		return x
	return targetcopy(original.right, cloned.right, target)

class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
		return targetcopy(original, cloned, target)


class Solution:

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


class Solution:

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


class Solution:
	cloned_target = None

	def traverse_tree(self, node, target):
		if not node:
			return
		if self.cloned_target is not None:
			return
		if node.val == target.val:
			self.cloned_target = node
			return
		self.traverse_tree(node.left, target)
		self.traverse_tree(node.right, target)

	def itr_traverse_tree(self, node, target):
		nodes_level = [node]
		while len(nodes_level) > 0:
			curr_node = nodes_level.pop()
			if curr_node is not None and target.val == curr_node.val:
				return curr_node
			if curr_node.left:
				nodes_level.append(curr_node.left)
			if curr_node.right:
				nodes_level.append(curr_node.right)
		return None

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
		return self.itr_traverse_tree(cloned, target)


class Solution:

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


class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
		nxt = [cloned]
		while True:
			curr = nxt.pop()
			if curr.val == target.val:
				return curr
			else:
				if curr.left:
					nxt.append(curr.left)
				if curr.right:
					nxt.append(curr.right)


class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:

		def dfs(original, cloned, target):
			if not original:
				return None
			if original == target:
				return cloned
			left = dfs(original.left, cloned.left, target)
			right = dfs(original.right, cloned.right, target)
			if left:
				return left
			else:
				return right
		result = dfs(original, cloned, target)
		return result


class Solution:
	find = None
	target = None

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
		self.target = target
		self.dfs(cloned)
		return self.find

	def dfs(self, tree: TreeNode):
		if not tree:
			return
		if tree.val == self.target.val:
			if tree.left and tree.right:
				if tree.left.val == self.target.left.val and tree.right.val == self.target.right.val:
					self.find = tree
					return
			if tree.left:
				if tree.left.val == self.target.left.val and (not tree.right) and (not self.target.right):
					self.find = tree
					return
			if tree.right:
				if tree.right.val == self.target.right.val and (not tree.left) and (not self.target.left):
					self.find = tree
					return
			if not tree.left and (not tree.right):
				if not self.target.left and (not self.target.right):
					self.find = tree
					return
		if tree.left:
			self.dfs(tree.left)
		if tree.right:
			self.dfs(tree.right)


class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
		q = [(original, cloned)]
		while q:
			(a, b) = q.pop()
			if a.val == target.val:
				return b
			else:
				if a.left is not None:
					q.append((a.left, b.left))
				if a.right is not None:
					q.append((a.right, b.right))


class Solution:

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


class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:

		def match(original, copy):
			if not original:
				return None
			if original == target:
				return copy
			return match(original.left, copy.left) or match(original.right, copy.right)
		return match(original, cloned)


class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
		return self.search(cloned, target)

	def search(self, node, target):
		if not node:
			return
		if node.val == target.val:
			return node
		return self.search(node.left, target) or self.search(node.right, target)


class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:

		def recur(orig, clon):
			if orig and (not clon) or (clon and (not orig)):
				return False
			if not orig and (not clon):
				return True
			if orig.val != clon.val:
				return False
			left = recur(orig.left, clon.left)
			right = recur(orig.right, clon.right)
			return left and right
		ans = None

		def dfs(original, cloned, target):
			nonlocal ans
			if original == target:
				isSame = recur(target, cloned)
				if isSame:
					ans = cloned
					return
			if original.left:
				dfs(original.left, cloned.left, target)
			if original.right:
				dfs(original.right, cloned.right, target)
		dfs(original, cloned, target)
		return ans


class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
		if not original:
			return

		def recur(ori, clo, target):
			if not ori:
				return
			if ori is target:
				return clo
			else:
				temp = recur(ori.left, clo.left, target)
				temp2 = recur(ori.right, clo.right, target)
				if temp:
					return temp
				if temp2:
					return temp2
		return recur(original, cloned, target)


class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:

		def original_clone(original, cloned, target):
			nonlocal a
			if original == None:
				return
			if original.val == target.val:
				a = cloned
				return
			original_clone(original.left, cloned.left, target)
			original_clone(original.right, cloned.right, target)
		a = None
		original_clone(original, cloned, target)
		return a


class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:

		def it(node):
			if node:
				yield node
				yield from it(node.left)
				yield from it(node.right)
		for (n1, n2) in zip(it(original), it(cloned)):
			if n1 == target:
				return n2


class Solution:
	ans = None

	def rootOrder(self, root, target):
		if not root:
			return 0
		print(root.val)
		if root.val == target.val:
			self.ans = root
		self.rootOrder(root.left, target)
		self.rootOrder(root.right, target)

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
		self.rootOrder(cloned, target)
		return self.ans


class Solution1:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
		p = deque([original])
		q = deque([cloned])
		while p and q:
			for _ in range(len(q)):
				node_o = p.popleft()
				node_c = q.popleft()
				if node_o == target:
					return node_c
				if node_o.left:
					p.append(node_o.left)
				if node_o.right:
					p.append(node_o.right)
				if node_c.left:
					q.append(node_c.left)
				if node_c.right:
					q.append(node_c.right)
		return None

class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:

		def preorder(root: TreeNode):
			yield root
			if root.left:
				yield from preorder(root.left)
			if root.right:
				yield from preorder(root.right)
		for (p, q) in zip(preorder(original), preorder(cloned)):
			if p == target:
				return q
		return None


class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
		q = [(original, cloned)]
		while q:
			(node_orig, node_clone) = q.pop()
			if node_orig is target:
				return node_clone
			if node_orig.left is not None:
				q.append((node_orig.left, node_clone.left))
			if node_orig.right is not None:
				q.append((node_orig.right, node_clone.right))


class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:

		def lis(root):
			if root:
				yield root
				yield from lis(root.left)
				yield from lis(root.right)
		for (a, b) in zip(lis(original), lis(cloned)):
			if a == target:
				return b


class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:

		def it(node):
			if node:
				yield node
				yield from it(node.left)
				yield from it(node.right)
		for (a, b) in zip(it(original), it(cloned)):
			if a == target:
				return b


class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:

		def dfs(node):
			if node:
				yield node
				yield from dfs(node.left)
				yield from dfs(node.right)
		for (it1, it2) in zip(dfs(original), dfs(cloned)):
			if it1 == target:
				return it2
		return -1


class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
		levels = collections.defaultdict(list)

		def move(node, lev, tl=None, ts=None):
			if node:
				levels[lev].append(node.val)
				if tl != None and len(levels[tl]) == ts:
					return node
				elif node.val == target.val:
					return (lev, len(levels[lev]))
				left = move(node.left, lev + 1, tl, ts)
				right = move(node.right, lev + 1, tl, ts)
				return left or right
		(tl, ts) = move(original, 0)
		levels = collections.defaultdict(list)
		return move(cloned, 0, tl, ts)


class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:

		def it(root: TreeNode) -> TreeNode:
			if root:
				yield root
				yield from it(root.left)
				yield from it(root.right)
		for (t1, t2) in zip(it(original), it(cloned)):
			if t1 == target:
				return t2


class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
		visited = set()
		node = self.dfs(visited, cloned, target)
		return node

	def dfs(self, visited, node: TreeNode, target: TreeNode):
		visited.add(node)
		if node.val == target.val:
			return node
		if node.left and node.left not in visited:
			left = self.dfs(visited, node.left, target)
			if left is not None:
				return left
		if node.right and node.right not in visited:
			right = self.dfs(visited, node.right, target)
			if right is not None:
				return right
		return None


def v(node, target_val, acc):
	if node is None:
		return []
	if node.val == target_val:
		return acc
	return v(node.left, target_val, acc + [-1]) + v(node.right, target_val, acc + [1])

class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
		d = v(original, target.val, [])
		node = cloned
		for step in d:
			if step == -1:
				node = node.left
			else:
				node = node.right
		return node


class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:

		def find_node(orignal, copy, find):
			if not orignal:
				return None
			if orignal == find:
				return copy
			return find_node(orignal.left, copy.left, find) or find_node(orignal.right, copy.right, find)
		return find_node(original, cloned, target)


class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:

		def inorder(root1, root2, target):
			if root1 == target:
				return root2
			if root1.left:
				left = inorder(root1.left, root2.left, target)
				if left:
					return left
			if root1.right:
				right = inorder(root1.right, root2.right, target)
				if right:
					return right
			return None
		return inorder(original, cloned, target)


from collections import deque

class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
		q = deque([(original, cloned)])
		while q:
			(node, cloned) = q.popleft()
			if node == target:
				return cloned
			if node.left:
				q.append((node.left, cloned.left))
			if node.right:
				q.append((node.right, cloned.right))
		return None


class Solution:

	def sameTree(self, s, t):
		if not s or not t:
			return s == t
		return s.val == t.val and self.sameTree(s.left, t.left) and self.sameTree(s.right, t.right)

	def findTarget(self, s, target):
		if not s:
			return [s] if not target else []
		res = [s] if s.val == target.val else []
		return res + self.findTarget(s.left, target) + self.findTarget(s.right, target)

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
		for l in self.findTarget(original, target):
			for r in self.findTarget(cloned, target):
				if self.sameTree(l, r):
					return r


from queue import Queue

class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
		if cloned == None:
			return None
		if cloned.val == target.val:
			return cloned
		cloned.left = self.getTargetCopy(original, cloned.left, target)
		if cloned.left != None:
			return cloned.left
		cloned.right = self.getTargetCopy(original, cloned.right, target)
		if cloned.right != None:
			return cloned.right
		return None


class Solution:

	def __init__(self):
		self.clone: TreeNode = None

	def find_possible_target(self, cloned: TreeNode, target: TreeNode):
		if not cloned:
			return None
		if cloned.val == target.val:
			return cloned
		possible_target = self.find_possible_target(cloned.left, target)
		if possible_target:
			return possible_target
		return self.find_possible_target(cloned.right, target)

	def are_they_copy(self, cloned: TreeNode, target: TreeNode) -> bool:
		if not cloned and (not target):
			return True
		if cloned and (not target):
			return False
		if not cloned and target:
			return False
		if not cloned.val == target.val:
			return False
		if not self.are_they_copy(cloned.left, target.left):
			return False
		return self.are_they_copy(cloned.right, target.right)

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
		if original is None or original == target:
			return cloned
		possible_target = self.find_possible_target(cloned, target)
		return possible_target


class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
		if not original or not cloned:
			return None
		stack = []
		stack.append((original, cloned))
		while stack:
			(orig, clone) = stack.pop()
			if orig == target:
				return clone
			if orig.right:
				stack.append((orig.right, clone.right))
			if orig.left:
				stack.append((orig.left, clone.left))


class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
		p = []
		ok = 0

		def dfs(i):
			if not i:
				return
			nonlocal ok
			if i == target:
				ok = 1
				return
			p.append(0)
			dfs(i.left)
			if ok:
				return
			else:
				p.pop()
			p.append(1)
			dfs(i.right)
			if ok:
				return
			else:
				p.pop()
		dfs(original)
		i = cloned
		for x in p:
			if x == 0:
				i = i.left
			else:
				i = i.right
		return i


class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
		if id(original) == id(target):
			return cloned
		q = [original]
		p = [cloned]
		idx = 0
		while idx < len(q):
			if id(q[idx]) == id(target):
				return p[idx]
			if q[idx].left:
				q.append(q[idx].left)
				p.append(p[idx].left)
			if q[idx].right:
				q.append(q[idx].right)
				p.append(p[idx].right)
			idx += 1
		return None


from collections import deque

class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
		x = cloned

		def clone(original, cloned, target, x):
			if original:
				if original == target:
					x = cloned
					return x
				return clone(original.left, cloned.left, target, x) or clone(original.right, cloned.right, target, x)
		return clone(original, cloned, target, x)


class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:

		def dfs(original, cloned, target):
			if original is None:
				return False
			if original.val == target.val:
				return cloned
			left = dfs(original.left, cloned.left, target)
			right = dfs(original.right, cloned.right, target)
			print(left, right)
			if left:
				return left
			if right:
				return right
		return dfs(original, cloned, target)


class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
		q = collections.deque()
		q.append([original, cloned])
		while q:
			(ori, cop) = q.popleft()
			if ori == target:
				return cop
			else:
				if ori.left:
					q.append([ori.left, cop.left])
				if ori.right:
					q.append([ori.right, cop.right])


class Solution:

	def getTargetCopy1(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:

		def dfs(node, lst):
			if node:
				lst.append(node)
				dfs(node.left, lst)
				dfs(node.right, lst)
		(original_stack, cloned_stack) = ([], [])
		dfs(original, original_stack)
		dfs(cloned, cloned_stack)
		for (l1, l2) in zip(original_stack, cloned_stack):
			if l1 == target:
				return l2

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:

		def it(node):
			if node:
				yield node
				yield from it(node.left)
				yield from it(node.right)
		for (n1, n2) in zip(it(original), it(cloned)):
			if n1 == target:
				return n2


class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
		nonlocal target_c, stack_o, stack_c
		target_c = None
		stack_o = [original]
		stack_c = [cloned]

		def helper():
			nonlocal target_c
			if len(stack_o) <= 0:
				return
			current_node_o = stack_o.pop()
			current_node_c = stack_c.pop()
			if current_node_o == None:
				helper()
				return
			if current_node_o.val == target.val:
				target_c = current_node_c
			stack_o.append(current_node_o.left)
			stack_c.append(current_node_c.left)
			stack_o.append(current_node_o.right)
			stack_c.append(current_node_c.right)
			helper()
		helper()
		return target_c


class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:

		def getpath(node1, node2):
			if node1.val == node2.val:
				return node1
			get_l = -1
			get_r = -1
			if node1.left is not None:
				get_l = getpath(node1.left, node2)
				if get_l != -1:
					return get_l
			if node1.right is not None:
				get_r = getpath(node1.right, node2)
				if get_r != -1:
					return get_r
				return -1
			if get_l == -1 and get_r == -1:
				return -1
		return getpath(cloned, target)


class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
		ol = self.toList(original)
		cl = self.toList(cloned)
		index = ol.index(target)
		return cl[index]

	def toList(self, root: TreeNode):
		if root is None:
			return []
		return self.toList(root.left) + [root] + self.toList(root.right)


class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
		return self.recur(cloned, target)

	def recur(self, node, target):
		if node.val == target.val:
			return node
		(a, b) = (None, None)
		if node.left:
			a = self.recur(node.left, target)
		if node.right:
			b = self.recur(node.right, target)
		return a or b


class Solution:

	def getResult(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
		if original == None or cloned == None or target == None:
			return None
		if original.val == target.val:
			return cloned
		left_result = self.getResult(original.left, cloned.left, target)
		if left_result:
			return left_result
		right_result = self.getResult(original.right, cloned.right, target)
		if right_result:
			return right_result
		return None

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
		result = self.getResult(original, cloned, target)
		return result


class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
		Q1 = []
		Q2 = []
		Q1.append(original)
		Q2.append(cloned)
		while len(Q1) > 0:
			current1 = Q1.pop(0)
			current2 = Q2.pop(0)
			if current1 == target:
				return current2
			if current1.left != None:
				Q1.append(current1.left)
			if current1.right != None:
				Q1.append(current1.right)
			if current2.left != None:
				Q2.append(current2.left)
			if current2.right != None:
				Q2.append(current2.right)


class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
		if cloned and target and original:
			if original.val == target.val:
				return cloned
			if self.getTargetCopy(original.left, cloned.left, target):
				return self.getTargetCopy(original.left, cloned.left, target)
			else:
				return self.getTargetCopy(original.right, cloned.right, target)


from collections import deque

class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
		num = target.val
		q = deque([cloned])
		while q:
			curr = q.popleft()
			if curr.val == num:
				return curr
			if curr.left:
				q.append(curr.left)
			if curr.right:
				q.append(curr.right)
		return None


class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:

		def dfs(root, target):
			if root and root.val == target:
				return root
			if root:
				return dfs(root.left, target) or dfs(root.right, target)
		return dfs(cloned, target.val)


class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:

		def dfs(onode, cnode, target):
			if onode:
				if onode.val == target.val:
					return cnode
				else:
					return dfs(onode.left, cnode.left, target) or dfs(onode.right, cnode.right, target)
		return dfs(original, cloned, target)


class Solution:

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


class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
		currNodes = [original]
		corrNodes = [cloned]
		while len(currNodes):
			currNode = currNodes.pop()
			corrNode = corrNodes.pop()
			if currNode is not None:
				if currNode is target:
					return corrNode
				if currNode.left is not None:
					currNodes.insert(0, currNode.left)
					corrNodes.insert(0, corrNode.left)
				if currNode.right is not None:
					currNodes.insert(0, currNode.right)
					corrNodes.insert(0, corrNode.right)
		return None


class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
		q = deque([cloned])
		while q:
			p = q.popleft()
			if p.val == target.val:
				return p
			q += [c for c in [p.left, p.right] if c]


class Stack:

	def __init__(self, stack: list):
		self.stack = stack

	def pop(self):
		if self.stack:
			return self.stack.pop(-1)
		else:
			return None

	def push(self, tree_node: TreeNode):
		self.stack.append(tree_node)

class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
		stack = Stack([cloned])
		while True:
			node = stack.pop()
			if node is None:
				break
			if node.val == target.val:
				return node
			if not node.right is None:
				stack.push(node.right)
			if not node.left is None:
				stack.push(node.left)
		return None


class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
		if original:
			if original == target:
				return cloned
			if original.left:
				outnode = self.getTargetCopy(original.left, cloned.left, target)
				if outnode:
					return outnode
			if original.right:
				outnode = self.getTargetCopy(original.right, cloned.right, target)
				if outnode:
					return outnode


from queue import Queue

class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
		q = Queue(maxsize=0)
		q.put((original, cloned))
		while q:
			(original, cloned) = q.get()
			if original == target:
				return cloned
			if original.left:
				q.put((original.left, cloned.left))
			if original.right:
				q.put((original.right, cloned.right))
		return None


class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
		self.res = None

		def dfs(node, target):
			if self.res:
				return
			if not node:
				return
			if node.val == target.val:
				self.res = node
			dfs(node.left, target)
			dfs(node.right, target)
		dfs(cloned, target)
		return self.res


class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:

		def dfs(original, cloned, target):
			if original == target:
				return cloned
			if original.left:
				l = dfs(original.left, cloned.left, target)
				if l:
					return l
			if original.right:
				r = dfs(original.right, cloned.right, target)
				if r:
					return r
		return dfs(original, cloned, target)


class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:

		def search(root, val):
			if root is None:
				return None
			if root.val == val:
				return root
			return search(root.left, val) or search(root.right, val)
		if original is None:
			return None
		return search(cloned, target.val)


class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
		o = {}

		def str_original(node):
			if not node:
				return '(None)'
			if node not in o:
				left = str_original(node.left)
				mid = '({})'.format(node.val)
				right = str_original(node.right)
				o[node] = '({}){}({})'.format(left, mid, right)
			return o[node]
		str_original(original)
		c = {}
		self.res = None

		def str_cloned(node):
			if not node:
				return '(None)'
			if node not in c:
				left = str_cloned(node.left)
				mid = '({})'.format(node.val)
				right = str_cloned(node.right)
				c[node] = '({}){}({})'.format(left, mid, right)
			if c[node] == o[target]:
				self.res = node
			return c[node]
		str_cloned(cloned)
		return self.res


class Solution:

	def getTargetCopy(self, o: TreeNode, c: TreeNode, t: TreeNode) -> TreeNode:
		if o == None:
			return
		if o == t:
			return c
		return self.getTargetCopy(o.left, c.left, t) or self.getTargetCopy(o.right, c.right, t)


class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
		if not original or original == target:
			return cloned
		l = self.getTargetCopy(original.left, cloned.left, target)
		if l:
			return l
		r = self.getTargetCopy(original.right, cloned.right, target)
		if r:
			return r


from queue import Queue

class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
		q = Queue()
		q.put(cloned)
		while q.qsize():
			node = q.get()
			if node.val == target.val:
				return node
			if node.left:
				q.put(node.left)
			if node.right:
				q.put(node.right)


class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
		queue = [cloned]
		visited = set()
		while queue:
			node = queue.pop()
			if node:
				if node.val == target.val:
					return node
				if node not in visited:
					visited.add(node)
					queue.append(node.left)
					queue.append(node.right)
		return False


class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
		queue = []
		queue.append(cloned)
		while queue:
			node = queue.pop(0)
			if node.val == target.val:
				return node
			if node.left:
				queue.append(node.left)
			if node.right:
				queue.append(node.right)
		return None


class Solution:

	def getTargetCopy(self, p: TreeNode, q: TreeNode, target: TreeNode) -> TreeNode:
		if not p and (not q):
			return
		if p == target:
			return q
		return self.getTargetCopy(p.left, q.left, target) or self.getTargetCopy(p.right, q.right, target)


class Solution:

	def pathToNode(self, tree: TreeNode, target: TreeNode, path: str) -> str:
		if not tree:
			return ''
		if target == tree:
			return path
		path.append('L')
		p = self.pathToNode(tree.left, target, path)
		if p:
			return p
		del path[-1]
		path.append('R')
		p = self.pathToNode(tree.right, target, path)
		if p:
			return p
		del path[-1]
		return ''

	def nodeAtPath(self, tree: TreeNode, path: str):
		if not path:
			return tree
		elif 'L' == path[0]:
			return self.nodeAtPath(tree.left, path[1:])
		elif 'R' == path[0]:
			return self.nodeAtPath(tree.right, path[1:])
		assert False

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
		path_to = self.pathToNode(original, target, [])
		return self.nodeAtPath(cloned, path_to)


class Solution:

	def getTargetCopy(self, rootA: TreeNode, rootB: TreeNode, inputA: TreeNode) -> TreeNode:
		q = deque([(rootA, rootB)])
		while q:
			(nodeA, nodeB) = q.popleft()
			if nodeA is inputA:
				return nodeB
			if nodeA.left is not None:
				q.append((nodeA.left, nodeB.left))
			if nodeA.right is not None:
				q.append((nodeA.right, nodeB.right))
		return None


class Solution:

	def find(self, copy, target):
		if copy:
			if copy.val == target:
				return copy
			a = self.find(copy.left, target)
			return a if a else self.find(copy.right, target)
		return None

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
		return self.find(cloned, target.val)


class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:

		def wtf(root, target):
			if root.val == target.val:
				return root
			if root.left:
				ans = wtf(root.left, target)
				if ans != None:
					return ans
			if root.right:
				ans = wtf(root.right, target)
				if ans != None:
					return ans
		return wtf(cloned, target)


from collections import deque

class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
		dq = deque()
		dq.append((original, cloned))
		while len(dq) > 0:
			(o, c) = dq.popleft()
			if o == target:
				return c
			if o.left is not None:
				dq.append((o.left, c.left))
			if o.right is not None:
				dq.append((o.right, c.right))
		return False


visited = set()

def dfs(cloned, target):
	if cloned.val not in visited:
		visited.add(cloned)
		if cloned.val == target.val:
			print(cloned)
			return cloned
		if cloned.left:
			a = dfs(cloned.left, target)
			if a:
				return a
		if cloned.right:
			a = dfs(cloned.right, target)
			if a:
				return a

class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
		found = dfs(cloned, target)
		return found


def traversal(original, cloned, target):
	if original == None:
		return None
	if original == target:
		return cloned
	res = traversal(original.left, cloned.left, target)
	if res != None:
		return res
	res = traversal(original.right, cloned.right, target)
	if res != None:
		return res
	return None

class Solution:

	def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
		return traversal(original, cloned, target)