LeetCode: 1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree
The Problem
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
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.
Constraints:
- The number of nodes in the
tree
is in the range[1, 104]
. - The values of the nodes of the
tree
are unique. target
node is a node from theoriginal
tree and is notnull
.
Solution
We opted for a recursive approach to tackle this problem, and upon evaluating our solution on the LeetCode platform, we achieved the following outcome:
Here's the code that led us to this result.
TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target) {
TreeNode *ans;
getTargetCopy(cloned, ans, target->val);
return ans;
}
void getTargetCopy(TreeNode* root, TreeNode *&ans, int target) {
if (root == nullptr) return;
if(root->val == target){
ans = root;
return;
} else {
getTargetCopy(root->left, ans, target);
getTargetCopy(root->right, ans, target);
}
}
Here's a step-by-step explanation of the code:
1. The main function TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target)
is the entry point. It takes three parameters:
original
: A pointer to the root of the original binary tree.cloned
: A pointer to the root of the cloned binary tree.target
: A pointer to the target node in the original tree that you want to find in the cloned tree.
2. Inside the getTargetCopy
function, there's a pointer ans
declared to store the result, which is initially uninitialized.
3. The getTargetCopy
function is then called with the cloned
tree, the ans
pointer, and the value of the target node from the original tree (target->val
). This initiates the search for the node in the cloned tree that matches the target value.
4. The getTargetCopy
function with three parameters is the recursive helper function:
- It first checks if the current node (
root
) isnullptr
, which means it has reached the end of a branch in the cloned tree. In that case, it returns, indicating the search is unsuccessful for this branch. - If the value of the current node (
root->val
) matches the target value, it means the target node from the original tree has been found in the cloned tree. In this case, it sets theans
pointer to point to this node and returns. This effectively terminates the search. - If the current node's value does not match the target, it continues the search recursively by calling
getTargetCopy
for both the left and right subtrees of the current node.
5. After the recursive search is complete, the main function returns the ans
pointer, which now points to the node in the cloned tree that corresponds to the target node in the original tree.