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: interview

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:
# 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 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)

# 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, 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


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


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

# 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:
        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)

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

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


# 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:
            return None
        
        stack = []
        
        def dfs( curr ):                                                
            
            if curr == target:
                return True
            
            if curr.left:
                stack.append(\"L\")
                if dfs(curr.left):
                    return True
                stack.pop()
                
            if curr.right:
                stack.append(\"R\")
                if dfs(curr.right):
                    return True
                stack.pop()      
                
            return False
        
        dfs(original)
        for d in stack:            
            if d == \"L\":
                cloned = cloned.left
            else:
                cloned = cloned.right
                            
                
        return cloned
            
            
            

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

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

# 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 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
        
            
            


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = 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))

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


# 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 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)


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


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

# 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 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)

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


# 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 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)

# 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 = [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)


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

class Solution:

    def find(self, copy, target):
        
        if not copy:
            return None

        if copy.val == target:
            return copy

        a = self.find(copy.left, target)
        return a or self.find(copy.right, target)

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



# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
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])
            


# 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
        
        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

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = 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:
            #self.node = clone
            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)
        #return self.node


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


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
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)

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


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
def targetcopy(original,cloned,target):
    if(original is None):
        return
    #print(original.val,cloned.val,target.val)
    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)

# 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 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


# 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 solve(node, value):
            \"\"\"recursively finds value in tree starting with parent node\"\"\"
            if not node:
                return None
            if node.val == value:
                return node
            left = solve(node.left, value)
            if left: 
                return left
            right = solve(node.right, value)
            if right:
                return right       
        
        return solve(cloned, target.val)
    
    
#             def solve(original,cloned,target):
#             if original == None:
#                 return None
#             if original == target:
#                 return cloned 
#             left = solve(original.left,cloned.left,target)
#             if left :
#                 return left 
#             right = solve(original.right, cloned.right,target)
#             if right :
#                 return right 
#         return solve(original,cloned,target)

# 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 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)


# 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:
        path = []
        def DFS(node):
            if not node:
                return False
            if node is target:
                return True
            if DFS(node.left):
                path.append(\"Left\")
                return True
            if DFS(node.right):
                path.append('Right')
                return True
            return False
        DFS(original)
        cHead = cloned
        for node in reversed(path):
            if node == \"Left\":
                cHead = cHead.left
            else:
                cHead = cHead.right
        return cHead
                

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

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)
            # nodes_level = [curr_node.left, curr_node.right]
        return None
            
    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
        # self.traverse_tree(cloned, target)
        return self.itr_traverse_tree(cloned, target)
        
        # return target


# 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 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

# 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:
        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)
            


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

# 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(original,cloned,target):
            if not original:
                return None
            # print(original.val)
            if original == target:
                # print('find')
                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


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

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)


# 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:
        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))
        
        


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

# 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:
        # time O(n); space O(h)
        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)

# 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:
        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)

# 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 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


# 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:
                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)

# 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 original is None:
            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 

# 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 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
        


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

        if left: 
            return left
        else:
            return right

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

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

from collections import deque

class Solution:
    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
        \"\"\"
        Focus on simple case of no repeated values, this means
        \"\"\"
        
        # assume node is in tree
        
        # find node in tree recursively
        
        def findNode(searchNode: TreeNode, target: TreeNode, current_directions = None) -> TreeNode:
            
            currentNode = searchNode
            if current_directions == None:
                current_directions = \"\"
            
            if currentNode == target:
                return current_directions
            elif currentNode == None:
                return None
            elif currentNode.left == None and currentNode.right == None:
                return None
            else:
                leftResult = findNode(currentNode.left, target, current_directions + \"L\")
                rightResult = findNode(currentNode.right, target, current_directions + \"R\")
                
                if leftResult:
                    return leftResult
                if rightResult:
                    return rightResult
            
            return None
        
        directions = findNode(original, target)
        print(directions)
        # traverse down tree from node
        nodeInNewTree = cloned

        for direction in directions:
            if direction == \"L\":
                nodeInNewTree = nodeInNewTree.left
            elif direction == \"R\":
                nodeInNewTree = nodeInNewTree.right

        return nodeInNewTree
            

\"\"\"        
        currentNode = cloned
        
        while currentNode != None:
            
            if target.val == currentNode.val:
                return currentNode
            elif target.val < currentNode.val: # go left
                currentNode = currentNode.left
            else: # go right
                currentNode = currentNode.right
\"\"\"

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

        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

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

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

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

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

# 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:
        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))

# 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 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


# 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 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

# 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 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

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

# 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 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

# 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(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

# 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:
        
        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)

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


# 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:
        
        levels = collections.defaultdict(list)
        def move(node, lev, tl = None, ts = None):
            if node:
                levels[lev].append(node)
                
                
                if tl!=None and len(levels[tl]) == ts:
                    return node
                elif node==target:
                    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)

# 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 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

# 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:
        # do a DFS on cloned, until come to target??
        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

# 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:
        return traverse_tree(cloned, target.val)
        
  

def traverse_tree(node: TreeNode, val: int) -> TreeNode:
    xNode = None
    
    if node == None:
        return;

    print(node.val);

    if node.val == val:
           print(\"cr {}\".format(node.val))
           return node

    xNode = traverse_tree(node.left, val)
    if xNode != None:
            print(\"left {}\".format(xNode))
            return xNode
    xNode = traverse_tree(node.right, val)
    if xNode != None:
            print(\"right {}\".format(xNode))
            return xNode
    
    print(\"Not found \")
    
    return None


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = 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:
        # Keep searching the original tree until we find target,
        # keeping track of how we moved to get there
        d = v(original, target.val, [])
        
        node = cloned
        for step in d:
            if step == -1:
                node = node.left
            else:
                node = node.right
        
        return node

# 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 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)

# 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 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

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = 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;

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = 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
        # #
        # no need to check if they are a copy or not
        # if self.are_they_copy(target, possible_target):
        #     return result
        # return None


# 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 traverse(node):
            if node:
                yield node
                yield from traverse(node.left)
                yield from traverse(node.right)
            
        for n1, n2 in zip(traverse(original), traverse(cloned)):
            if n1 == target:
                return n2

# 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
        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))


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

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(list(preorder(original)), list(preorder(cloned))):
            if p == target: return q
        return None

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

class Solution:
    res = TreeNode
    
    def dfs(self, original: TreeNode, cloned: TreeNode, target: TreeNode):
        if original is target:
            self.res = cloned
            return
        print(original.val)
        
        if original.left is None and original.right is None:
            return
        
        if original.left != None:
            print(\"has left\")
            self.dfs(original.left, cloned.left, target)
        if original.right != None:
            print(\"has right\")
            self.dfs(original.right, cloned.right, target)
    
    
    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
        self.dfs(original, cloned, target)
        return self.res
    

# 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:
        stack = []
        stack.append(cloned)
        
        while stack:
            v = stack.pop()
            if v.val == target.val:
                return v
            
            if v.left:
                stack.append(v.left)
            if v.right:
                stack.append(v.right)


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

# 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 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)

# 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(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)

# 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:
        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] )


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

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:
        # if original == target:
        #     return cloned
        # stack = [(original, cloned)]
        # while stack:
        #     node1, node2 = stack.pop()
        #     if node1 == target:
        #         return node2
        #     if node1.right:
        #         stack.append((node1.right, node2.right))
        #     if node1.left:
        #         stack.append((node1.left, node2.left))
        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

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

# 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:
        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(node_o.right,node_c.right)
        helper()
        #print(target_c)
        return target_c


# 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 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)

# 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:
        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)
        


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

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

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

# 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:
        '''Q=[]
        Q.append(original)
        Q.append(\"LVL\")
        level=1
        pos=1
        my_dict={}
        while len(Q)>1:
            current=Q.pop(0)
            if current==\"NO\":
                Q.append(\"NO\")
                Q.append(\"NO\")
                pos+=2
                continue
            if current==target:
                my_dict[level]=pos
                break
            if current==\"LVL\":
                level+=1
                pos=0
                Q.append(\"LVL\")
                continue
            
            if current.left!=None:
                Q.append(current.left)
                pos+=1
            else:
                Q.append(\"NO\")
                pos+=1
            
            if current.right!=None:
                Q.append(current.right)
                pos+=1
            else:
                Q.append(\"NO\")
                pos+=1
        print(my_dict)
        
        Q=[]
        Q.append(cloned)
        Q.append(\"LVL\")
        level=1
        pos=1
        while len(Q)>1:
            current=Q.pop(0)
            if current==\"NO\":
                Q.append(\"NO\")
                Q.append(\"NO\")
                pos+=2
                continue
            if level in my_dict and pos==my_dict[level]:
                
                return current
            if current==\"LVL\":
                level+=1
                pos=0
                Q.append(\"LVL\")
                continue
            
            if current.left!=None:
                Q.append(current.left)
                pos+=1
            else:
                Q.append(\"NO\")
                pos+=1
            
            if current.right!=None:
                Q.append(current.right)
                pos+=1
            else:
                Q.append(\"NO\")
                pos+=1
                
           '''
        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)
            
        
        
        
        
        
        
        
        
        
        
        
        
                


# 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 or not target:
            return None
        if cloned.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)
        


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


# 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 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)
            
        
            


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
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

# 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:
        # 4:41pm
        
#         def sameTree(root1, root2):
#             if not root1 and not root2:
#                 return True
            
#             if root1 and root2:
#                 return root1.val == root2.val and sameTree(root1.left, root2.left) and sameTree(root2.right, root2.right)
        
#         if not original or not cloned:
#             return None
        
#         if original.val == cloned.val == target.val and sameTree(original.left, cloned.left) and sameTree(original.right, cloned.right):
#             return cloned
        
#         return self.getTargetCopy(original.left, cloned.left, target) or self.getTargetCopy(original.right, cloned.right, target)

        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)
        


# 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 original == target:
            return cloned

        self.path = \"\"
        self.found = False
        def getTargetCopyRecursive(root, path, target):
            if root and not self.found:
                if root == target:
                    self.found = True
                    self.path = path
                else:
                    if root.right and not self.found:
                        getTargetCopyRecursive(root.right, path + \"R\", target)
                    if root.left and not self.found:
                        getTargetCopyRecursive(root.left, path + \"L\", target)

        getTargetCopyRecursive(original,\"\",target)

        root = cloned
        for letter in self.path:
            if letter == \"R\":
                root = root.right
            elif letter == \"L\":
                root = root.left

        return root

# 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(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)

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


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


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


# 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:
        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]


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
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

# 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 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

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


# 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(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)


# 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 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)
            
            


# 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:
        
        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)
        #print(o[target])
        
        return self.res


# 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, 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)

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

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

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

from queue import Queue

class Solution:
    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
        
        # unique node val
        
        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)

# 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:
        return self.search(cloned, target)
    
    def search(self, node, target):
        if node == None:
            return None
        if node.val == target.val:
            return node
        n = self.search(node.left, target)
        if n:
            return n
        n = self.search(node.right, target)
        return n


class Solution:
    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
        self.path = 0
        self.targetNum = target.val
        self.dfs(original, 1)
        ansPath = str(bin(self.path))[3:]
        for i in ansPath:
            if(i == \"1\"):
                cloned = cloned.left
            else:
                cloned = cloned.right
        return cloned
    
    def dfs(self, curr, path):
        if(curr.val == self.targetNum):
            self.path = path
            return
        if(curr.left):
            self.dfs(curr.left, (path<<1) + 1)
        if(curr.right):
            self.dfs(curr.right, path<<1)

# 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 = [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

        


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

class Solution:
    def __init__(self):
        self.node = None
    def findtarget(self,org,clone,target):
        
        if not org or not clone:
            return 
        
        
        if org.val==target.val==clone.val:
            self.node = clone
            return 
        self.findtarget(org.left,clone.left,target)  
        self.findtarget(org.right,clone.right,target)
          
    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
        
        self.findtarget(original,cloned,target)
        return self.node

# 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 = []
        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
                    
            
            
            
        
        
        


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

class Solution:
    #n=n=n=n=n=n=n=
    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)

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

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, [])
        # assert path_to
        return self.nodeAtPath(cloned, path_to)

# 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, 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
    


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = 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) 



# 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 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)

# 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 original == target:
            return cloned
        node = None
        if original.left:
            node = self.getTargetCopy(original.left, cloned.left, target)
        if not node and original.right:
            node = self.getTargetCopy(original.right, cloned.right, target)
        return node
            
        \"\"\"
        def _findNodeAndReturnPath(root, tgt, path):
            if not root:
                return ''
            if root == tgt:
                return path
            #print(' looking left for node %d' % root.val)
            lpath = _findNodeAndReturnPath(root.left, tgt, path + 'L')
            if lpath:
                #print(' found target at node %d, Lpath=%s' % (root.val, lpath))
                
                return lpath
            #print(' looking right for node %d' % root.val)
            rpath = _findNodeAndReturnPath(root.right, tgt, path + 'R')
            if not rpath:
                return ''
            #print(' found target at node %d, Rpath=%s' % (root.val, rpath))
            return rpath
        #print(' path to node=%d is %s' % (target.val, 'path'))
        path = _findNodeAndReturnPath(original, target, '')
        print(' path to node=%d is %s' % (target.val, path))
        curr = cloned
        for xc in path:
            if xc == 'L':
                curr = curr.left
            else: # if xc == 'R':
                curr = curr.right
        return curr
        \"\"\"

from collections import deque
# 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:
        # 1. dfs 38% time
        # stack = []
        # stack.append((original, cloned))
        # while len(stack) > 0:
        #     o, c = stack.pop()
        #     if o == target: # could compare value instead
        #         return c
        #     if o.left is not None: stack.append((o.left, c.left))
        #     if o.right is not None: stack.append((o.right, c.right))
        # return False # not found - impossible
    
    
        # 2. bfs
        dq = deque()
        dq.append((original, cloned))
        while len(dq) > 0:
            o, c = dq.popleft()
            if o == target: # could compare value instead
                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 # not found - impossible
    # todo - try recursion implementation


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


visited = set()
def dfs(cloned, target):
    
    if cloned.val not in visited:
        #print(f\"looking at {cloned}\")
        visited.add(cloned)
        #print(f\"added {cloned} to visited\")
        
        if cloned.val == target.val:
            # print(f\"Found the target! {cloned}\")
            # print(\"Returning cloned...\")
            print(cloned)
            return cloned
        
        if cloned.left:
            #print(\"calling dfs on cloned.left\")
            a = dfs(cloned.left, target)
            if a:
                return a
        
        if cloned.right:
            #print(\"calling dfs on cloned.right\")
            a = dfs(cloned.right, target)
            if a:
                return a
            

    

    
    
class Solution:
    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
        # print(f\"original {original}\")
        # print(f\"cloned {cloned}\")
        # print(f\"target {target}\")
        
        found = dfs(cloned, target)
        
        # print(f\"found: {found}\")
        
        return found
        


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

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)        

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