Find a Corresponding Node of a Binary Tree in a Clone of That Tree
You can solve this problem by performing a depthfirst search (DFS) on both trees simultaneously.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 class Solution:
def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) > TreeNode:
# Create a stack for original tree and cloned tree
stack_original = [original]
stack_cloned = [cloned]
# Perform DepthFirst Search on both trees
while stack_original:
node_original = stack_original.pop()
node_cloned = stack_cloned.pop()
# If the current node in the original tree is the target, return the corresponding node in the cloned tree
if node_original is target:
return node_cloned
# If the node in the original tree has a left child, add it to the stack, along with its counterpart in the cloned tree
if node_original.left:
stack_original.append(node_original.left)
stack_cloned.append(node_cloned.left)
# If the node in the original tree has a right child, add it to the stack, along with its counterpart in the cloned tree
if node_original.right:
stack_original.append(node_original.right)
stack_cloned.append(node_cloned.right)

In the code, we depthfirst search (DFS) on the original tree and the cloned tree at the same time. When we find the target node in the original tree, we return the corresponding node in the cloned tree. As we’re exploring the trees in the same order, the nodes we’re examining in the cloned tree will always correspond to the nodes we’re examining in the original tree.