Finding a node in a cloned tree using DFS

Anthony George 0
Viewed 23

I am trying the LeetCode problem1379. 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.

This is my code:

class Solution {
public: 

    TreeNode* ans = NULL ; 

    TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target) {
       // if(cloned == NULL){return cloned ;}
        if(cloned == NULL){return cloned ;}
        
       // if(cloned->val == target->val){
       //  return cloned ; 
       //  }

        if(cloned->val == target->val){
             ans = cloned ;
        } 
         // return  getTargetCopy(original,cloned->left ,target) ;
         // return  getTargetCopy(original,cloned->right,target) ;  
        getTargetCopy(original,cloned->left ,target) ; 
        getTargetCopy(original,cloned->right,target) ;  
        return ans ; 
    }
};

The commented out part was my initial code but it returned wrong answer

Your input

[7,4,3,null,null,6,19]
3

Output

null

Expected

3

Help me understand the problem in my code

depth-first-search tree c++
1 Answers

Some issues:

With these (now commented) lines:

    return  getTargetCopy(original,cloned->left ,target) ;
    return  getTargetCopy(original,cloned->right,target) ;

...execution would never get to that second line, as the first line would end the function.

These (now commented) lines:

    if(cloned->val == target->val){
        return cloned ; 
    }

...are fine: once you have found the target value, there is no need to do anything else in this function, and so it is fine to return the node. This is better than setting ans to that node and still make some (unnecessary) recursive call(s).

What is missing here is getting the value from the first recursive call, and deciding whether that call successfully found the target value or not. In case it found it, there is no more need for a second recursive call. In case it didn't find it, then the second recursive call is needed. Finally, the return value you get from either recursive call, should be returned back as the current function's return value.

So:

class Solution {
public:
    TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target) {
        if (cloned == nullptr || cloned->val == target->val) {
             return cloned;
        } 
        TreeNode *ans = getTargetCopy(original,cloned->left ,target) ; 
        if (ans != nullptr) {
            return ans;
        }
        return getTargetCopy(original,cloned->right,target) ;  
    }
};
trincot0
Related