首先使用先序遍历的方法:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

class Solution {
public:
    TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target) {
        if(original == NULL || cloned == NULL)
            return NULL;
        
        if(original == target)
            return cloned;
        
        TreeNode* left = getTargetCopy(original->left,cloned->left,target);
        if(left) return left;
        
        
        TreeNode* right = getTargetCopy(original->right,cloned->right,target);
        if(right) return right;
        
        return NULL;
    }
};

运行效率：

Runtime: 464 ms, faster than 96.08% of C++ online submissions for Find a Corresponding Node of a Binary Tree in a Clone of That Tree.
Memory Usage: 163.8 MB, less than 96.97% of C++ online submissions for Find a Corresponding Node of a Binary Tree in a Clone of That Tree.

使用BFS方法：

class Solution {
public:
    TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target) {
        queue<TreeNode *> ori,clo;
        ori.push(original);
        clo.push(cloned);
        
        while(!ori.empty() && !clo.empty())
        {
            int size = ori.size();
            for(int i = 0;i < size;i++)
            {
                TreeNode* curr_ori = ori.front();
                TreeNode* curr_clo = clo.front();
                if(curr_ori == target)
                    return curr_clo;
                ori.pop(),clo.pop();
                if(curr_ori->left) ori.push(curr_ori->left);
                if(curr_ori->right) ori.push(curr_ori->right);
                
                if(curr_clo->left) clo.push(curr_clo->left);
                if(curr_clo->right) clo.push(curr_clo->right);

            }
        }
        
        return NULL;
    }
};

运行效率:

Runtime: 480 ms, faster than 91.32% of C++ online submissions for Find a Corresponding Node of a Binary Tree in a Clone of That Tree.
Memory Usage: 165.8 MB, less than 85.08% of C++ online submissions for Find a Corresponding Node of a Binary Tree in a Clone of That Tree.