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.
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
Constraints:
tree is in the range [1, 104].tree are unique.target node is a node from the original tree and is not null.
Follow up: Could you solve the problem if repeated values on the tree are allowed?
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.
The function getTargetCopy checks if the current node in the original tree is the target. If so, it returns the corresponding node in the cloned tree. Otherwise, it recursively searches the left subtree, then the right subtree.
Java
C++
C
C#
JavaScript
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.
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.
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.
Java
C++
C
C#
JavaScript
Time Complexity: O(N)
Space Complexity: O(W), where W is the maximum width of the tree.
| Approach | Complexity |
|---|---|
| Approach 1: Recursive DFS | Time Complexity: O(N), where N is the number of nodes in the tree because each node is visited once. |
| Approach 2: Iterative BFS | Time Complexity: O(N) |
Find a Corresponding Node of a Binary Tree in a Clone of That Tree | Live Coding | Leetcode - 1379 • Algorithms Made Easy • 5,482 views views
Watch 9 more video solutions →Practice Find a Corresponding Node of a Binary Tree in a Clone of That Tree with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor