说在前面

🎈不知道大家对于算法的学习是一个怎样的心态呢？为了面试还是因为兴趣？不管是出于什么原因，算法学习需要持续保持。

题目描述

给你两棵二叉树，原始树 original 和克隆树 cloned，以及一个位于原始树 original 中的目标节点 target。

其中，克隆树 cloned 是原始树 original 的一个 副本 。

请找出在树 cloned 中，与 target 相同 的节点，并返回对该节点的引用（在 C/C++ 等有指针的语言中返回 节点指针，其他语言返回节点本身）。

注意： 你 不能 对两棵二叉树，以及 target 节点进行更改。只能 返回对克隆树 cloned 中已有的节点的引用。

示例 1:

输入: tree = [7,4,3,null,null,6,19], target = 3
输出: 3
解释: 上图画出了树 original 和 cloned。target 节点在树 original 中，用绿色标记。答案是树 cloned 中的黄颜色的节点（其他示例类似）。

示例 2:

输入: tree = [7], target =  7
输出: 7

示例 3:

输入: tree = [8,null,6,null,5,null,4,null,3,null,2,null,1], target = 4
输出: 4

提示：

• 树中节点的数量范围为 [1, 10^4] 。
• 同一棵树中，没有值相同的节点。
• target 节点是树 original 中的一个节点，并且不会是 null 。

进阶： 如果树中允许出现值相同的节点，将如何解答？

解题思路

因为这道题目中二叉树的值都是唯一的，所以我们可以直接判断值是否相等来获取到相同的节点。

• 递归遍历二叉树
• 判断节点值是否和木匾节点值相等
• 将找到的节点返回

如果已经找到目标节点或者传入的节点不存在，则直接返回。如果当前节点的值与target的值相等，那么将该节点存储在外部变量res中，表示找到了目标节点。
如果当前节点的值不是目标值，那么递归地在当前节点的左子树和右子树中查找目标节点。

函数开始时初始化res为null，表示还没有找到目标节点。然后调用getNode函数，从cloned树的根节点开始递归搜索。最后，返回res，它将是找到的目标节点，或者在没有找到目标节点的情况下仍然是null。

AC代码

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} original
 * @param {TreeNode} cloned
 * @param {TreeNode} target
 * @return {TreeNode}
 */

var getTargetCopy = function (original, cloned, target) {
  let res = null;
  const getNode = (node) => {
    if (res || !node) return;
    if (node.val === target.val) res = node;
    getNode(node.left);
    getNode(node.right);
  };
  getNode(cloned);
  return res;
};

公众号

关注公众号『前端也能这么有趣』，获取更多有趣内容。

说在后面

🎉 这里是 JYeontu，现在是一名前端工程师，有空会刷刷算法题，平时喜欢打羽毛球 🏸 ，平时也喜欢写些东西，既为自己记录 📋，也希望可以对大家有那么一丢丢的帮助，写的不好望多多谅解 🙇，写错的地方望指出，定会认真改进 😊，偶尔也会在自己的公众号『前端也能这么有趣』发一些比较有趣的文章，有兴趣的也可以关注下。在此谢谢大家的支持，我们下文再见 🙌。