Problem Statement : https://leetcode.com/explore/challenge/card/january-leetcoding-challenge-2021/579/week-1-january-1st-january-7th/3590/
We can do any tree traversal and check the target node value with the current node value and if same we can return it.
Here we used DFS traversal, if you are not aware of it please go through the below link.
https://en.wikipedia.org/wiki/Depth-first_search#:~:text=Depth%2Dfirst%20search%20(DFS),along%20each%20branch%20before%20backtracking.
Note: Since they didn't mentioned about duplicates no need of original tree.
But the best pratice would be comparing with original tree also.
The follwing are two approaches with and wihtout using original tree -
class Solution {
public:
TreeNode* dfs(TreeNode* root, TreeNode* target) {
if(!root) return nullptr;
if(root -> val == target -> val) return root;
TreeNode* left = dfs(root -> left, target);
TreeNode* right = dfs(root -> right, target);
if(left) return left;
return right;
}
TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target) {
return dfs(cloned, target -> val);
}
};class Solution {
public:
TreeNode* dfs(TreeNode* original, TreeNode* cloned, TreeNode* target) {
if(!original) return nullptr;
if(original == target) return cloned;
TreeNode* left = dfs(original -> left, cloned -> left, target);
TreeNode* right = dfs(original -> right, cloned -> right ,target);
if(left) return left;
return right;
}
TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target) {
return dfs(original, cloned, target);
}
};Upvote if you like.
Thank you.