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.
1public TreeNode 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}Uses recursive DFS to locate the target node in the original tree and returns the corresponding node from the cloned tree. It traverses left before right.
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.