题目大意：
给你两颗二叉树 original 和cloned，以及一个 original 树种的节点对象 target 。
cloned树是 original树的拷贝。
请返回 cloned 树种相对应的 target 节点对象。
注意，你不能改变2棵树的内容以及 target节点，另外返回结果必须是cloned树中的对象。
进阶：如果每棵树中存在数值相同的节点，你该如何处理
示例1：
输入: tree = [7,4,3,null,null,6,19], target = 3 输出: 3 解释: 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.
示例2：
输入: tree = [7], target = 7 输出: 7
示例3：
输入: tree = [8,null,6,null,5,null,4,null,3,null,2,null,1], target = 4 输出: 4
示例4：
输入: tree = [1,2,3,4,5,6,7,8,9,10], target = 5 输出: 5
示例5：
输入: tree = [1,2,null,3], target = 2 输出: 2
提示：
- 二叉树中节点值的范围在 [1, 10^4] 之间
- 每颗树中所有节点的值是唯一的
-
target节点是original树中的节点，并且它是非空的
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1379
解题思路分析：
对于二叉树题目，bfs或者dfs是非常好的解题方案，本题也不例外，我们可以使用dfs深度优先搜索来解题。dfs时，我们将original 和cloned两棵树的当前节点同时传入dfs方法中，如果当前original节点与target相同，那么，当前 cloned 节点即是返回结果。反之继续向左右子节点进行dfs。
实现代码：
public final TreeNode getTargetCopy(final TreeNode original,
final TreeNode cloned, final TreeNode target) {
// 如果original当前节点等于target节点，返回对应的cloned节点
if(original.equals(target)) return cloned;
// 如果左子节点不为空
if(original.left!=null){
// dfs至左子节点
TreeNode left=getTargetCopy(original.left,cloned.left,target);
// 如果dfs结果不为空，返回该结果
if(left!=null) return left;
}
// 如果右子节点不为空
if(original.right!=null){
// dfs至右子节点，并返回该结果
return getTargetCopy(original.right,cloned.right,target);
}
return null;
}本题解法执行时间为0ms。
Runtime: 0 ms, faster than 100.00% of Java online submissions for Find a Corresponding Node of a Binary Tree in a Clone of That Tree.
Memory Usage: 44.8 MB, less than 100.00% of Java online submissions for Find a Corresponding Node of a Binary Tree in a Clone of That Tree.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1379-find-a-corresponding-node-of-a-binary-tree-in-a-clone-of-that-tree-解题思路分析/