Sponsored
Sponsored
This approach involves using a recursive depth-first search to simultaneously traverse both the original and cloned trees. When you find the target node in the original tree, return the corresponding node in the cloned tree.
Time Complexity: O(N), where N is the number of nodes in the tree because each node is visited once.
Space Complexity: O(H), where H is the height of the tree due to the recursion stack.
1TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target) {
2 if (original == NULL) return NULL;
3 if (original == target) return cloned;
4 TreeNode* left = getTargetCopy(original->left, cloned->left, target);
5 if (left != NULL) return left;
6 return getTargetCopy(original->right, cloned->right, target);
7}In this C code, the function recursively finds the target by checking the left and right subtrees, returning the mirrored node from the cloned tree.
Utilizing a queue, this approach explores both the original and cloned trees in parallel level-by-level. Once the target node is located in the original tree, the corresponding node in the cloned tree is returned.
Time Complexity: O(N)
Space Complexity: O(W), where W is the maximum width of the tree.
This Java function uses two queues to perform a synchronized BFS on original and cloned trees. On finding the target in the original tree, it returns the corresponding node from the cloned tree.