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 == nullptr) return nullptr;
3 if (original == target) return cloned;
4 TreeNode* left = getTargetCopy(original->left, cloned->left, target);
5 if (left != nullptr) return left;
6 return getTargetCopy(original->right, cloned->right, target);
7}This C++ function checks if the current node is the target and returns the corresponding node in the cloned tree. It employs a recursive DFS on both subtrees.
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 getTargetCopy function uses a queue to iteratively traverse the trees. It dequeues a pair of nodes, checks the original against the target, and enqueues children if necessary.