题目

1379. 找出克隆二叉树中的相同节点

分析

这道题目其实利用的是递归的思想，同时遍历两棵树即可。具体流程（下面所讲解的流程基于的前提一定是两棵树一起遍历哦）：

• 如果 original 为空节点，直接返回 null；
• 如果 original == target ，说明我们找到了对应的节点，直接返回 cloned；
• 没找到的话，递归遍历左子树，即执行getTargetCopy(original.left,cloned.left,target)，如果有返回值，代表左子树找到了，直接返回找到的值，右子树不用遍历了。
• 左子树没找到，遍历右子树，即执行 getTargetCopy(original.right,cloned.right,target)，如果有返回值，代表右子树找到了，直接返回找到的值。
• 否则，左右子树都没找到 且 original != target，直接返回 null；

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

class Solution {
    public final TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target) {
        // 同时遍历两课树
        if(original == null) return null;
        if(original == target) {
            return cloned;
        }
        TreeNode left = getTargetCopy(original.left,cloned.left,target);
        if(left != null) {
            return left;
        }
        
        TreeNode right = getTargetCopy(original.right,cloned.right,target);
        if(right != null) {
            return right;
        }
        return null;
    }
}