解法一：广度优先搜索

提示中说明了树中没有两个结点有相同的值，那么找相同结点其实就是遍历并且比较结点的val属性的过程。original结点我觉得其实完全用不到。先用深度优先搜索做一遍。

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  11. class Solution {
  12.     public final TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target) {
  13.         if (cloned == null) {
  14.             return null;
  15.         }
  16.         Queue<TreeNode> queue = new LinkedList<>();
  17.         queue.offer(cloned);
  18.         TreeNode tmp;
  19.         while (!queue.isEmpty()) {
  20.             tmp = queue.poll();
  21.             if (tmp.val == target.val) {
  22.                 return tmp;
  23.             }
  24.             if (tmp.left != null) {
  25.                 queue.offer(tmp.left);
  26.             }
  27.             if (tmp.right != null) {
  28.                 queue.offer(tmp.right);
  29.             }
  30.         }
  31.         return null;
  32.     }
  33. }

解法二：深度优先搜索

看了下提交结果，似乎这道题用深搜会更快一些，用深搜也写一遍。

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  11. class Solution {
  12.     public final TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target) {
  13.         if (cloned == null) {
  14.             return null;
  15.         }
  16.         if (cloned.val == target.val) {
  17.             return cloned;
  18.         }
  19.         TreeNode ans = null;
  20.         if (cloned.left != null) {
  21.             ans = getTargetCopy(original, cloned.left, target);
  22.         }
  23.         if (ans != null) {
  24.             return ans;
  25.         } else {
  26.             return getTargetCopy(original, cloned.right, target);
  27.         }
  28.     }
  29. }