LeetCode 1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree

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.

Follow up: Solve the problem if repeated values on the tree are allowed.

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
Example 4:

Input: tree = [1,2,3,4,5,6,7,8,9,10], target = 5
Output: 5
Example 5:

Input: tree = [1,2,null,3], target = 2
Output: 2

Constraints:

The number of nodes in the tree is in the range [1, 10^4].
The values of the nodes of the tree are unique.
target node is a node from the original tree and is not null.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

static auto x = []()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    return 0;
}();
class Solution {
public:
    TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target) {
        if(original==target){
            return cloned;
        }
        if(original->left){
            TreeNode* tmp = getTargetCopy(original->left,cloned->left,target);
            if(tmp){
                return tmp;
            }
        }
        if(original->right){
            TreeNode* tmp = getTargetCopy(original->right,cloned->right,target);
            if(tmp){
                return tmp;
            }
        }
        return NULL;
    }
};


20 Replies to “LeetCode 1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree”

  1. Thank you for the sensible critique. Me and my friend were just preparing to do some research about this. We got a book from our local library but I think I learned better from this post. I am very glad to see such fantastic information being shared freely out there.. Ricca Uriel Lemmuela

  2. Greetings! Very helpful advice in this particular article! It is the little changes which will make the greatest changes. Thanks a lot for sharing! Jodee Agosto Evelin

  3. After exploring a few of the blog articles on your site, I truly like your technique of blogging. I bookmarked it to my bookmark webpage list and will be checking back soon. Take a look at my web site as well and let me know your opinion. Antonia Rogers Layne

  4. Hey There. I found your blog using msn. This is a really well written article. I will make sure to bookmark it and return to read more of your useful info. Thanks for the post. I will certainly return.| Karisa Web Rhody

  5. Hello there. I found your blog via Google whilst looking for a comparable matter, your web site got here up. It seems to be good. I have bookmarked it in my google bookmarks to come back then. Reggi Shep Cletus

  6. Normally I do not read article on blogs, but I would like to say that this write-up very forced me to try and do so! Your writing style has been surprised me. Thank you, quite great article.| Jacqueline Dino Harmon

  7. Thanks for a marvelous posting! I genuinely enjoyed reading it, you will be a great author. I will make certain to bookmark your blog and will eventually come back later on. I want to encourage that you continue your great writing, have a nice day! Caressa Vladamir Merry

Leave a Reply

Your email address will not be published. Required fields are marked *