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

Leetcode link

解题思路

题目给了我们两棵一模一样的树，并且将一个指针 target 指向了原树的其中一个节点，要求我们找到拷贝树上对应的节点

这种题目一般用 bfs 或者 dfs 来求解，一种简单的思路就是：

• 遍历拷贝的树，当遇到与 target 指针指向的值一样的树节点的时候，返回拷贝树对应的节点指针

但是这个思路有一个限制条件，就是树上不能有两个值相同的节点。

所以在这里我们用同时遍历两棵树的方法，详情见代码：

C++

/**
 * 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) {
        TreeNode* res = nullptr;
        dfs(original, cloned, target, res);
        return res;
    }
  // 记得这里的 res 需要使用引用，因为我们需要记录 res 指针存放的地址
    void dfs(TreeNode* original, TreeNode* cloned, TreeNode* target, TreeNode*& res) {
      // 如果已经找到了 res，就没必要继续下去了
        if(original == nullptr || res != nullptr) {
            return;
        }
      // 当原树的节点等于目标节点的时候，拷贝树的对应节点就是我们的解
        if(original == target) {
            res = cloned;
            return ;
        }

        dfs(original->left, cloned->left, target, res);
        dfs(original->right, cloned->right, target, res);
    }
};