原文链接: https://leetcode-cn.com/problems/find-a-corresponding-node-of-a-binary-tree-in-a-clone-of-that-tree

英文原文

Given two binary trees original and cloned and given a reference to a node target in the original tree.

The cloned tree is a copy of the original tree.

Return a reference to the same node in the cloned tree.

Note that you are not allowed to change any of the two trees or the target node and the answer must be a reference to a node in the cloned tree.

 

Example 1:

Input: tree = [7,4,3,null,null,6,19], target = 3
Output: 3
Explanation: 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.

Example 2:

Input: tree = [7], target =  7
Output: 7

Example 3:

Input: tree = [8,null,6,null,5,null,4,null,3,null,2,null,1], target = 4
Output: 4

Example 4:

Input: tree = [1,2,3,4,5,6,7,8,9,10], target = 5
Output: 5

Example 5:

Input: tree = [1,2,null,3], target = 2
Output: 2

 

Constraints:

• The number of nodes in the tree is in the range [1, 104].
• The values of the nodes of the tree are unique.
• target node is a node from the original tree and is not null.

 

Follow up: Could you solve the problem if repeated values on the tree are allowed?

中文题目

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

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

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

 

注意：

1. 你 不能 对两棵二叉树，以及 target 节点进行更改。
2. 只能 返回对克隆树 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

示例 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 中的一个节点，并且不会是 null 。

通过代码

高赞题解

解题思路

original树和cloned树的结构，以及所有节点对应的值都是一模一样。基本可以理解成两个”相同”的树（但是内存地址不同，本质上并不一样）。

要在original树中来寻找target，自然想到的就是遍历original树。那么正常的前中后序遍历，应该选择哪一个呢？

前序遍历。

因为只要original和target相同，则表示对应的cloned就是我们想要的节点。这个遍历过程，和左右子树并没有关系。所以我们选择前序遍历。

递归和非递归的写法见代码。

当然，层次遍历同样能解决问题。同时对两棵树进行层次遍历即可。只是要多加一个辅助队列，用来存储cloned树节点了

前序遍历递归代码

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 res = getTargetCopy(original.left,cloned.left,target);
        if (res != null){
            return res;
        }
        // 递归右子树
        res = getTargetCopy(original.right,cloned.right,target);
        if (res != null){
            return res;
        }
        return null;
    }
}

前序遍历非递归代码

class Solution {
    public final TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target) {
        Deque<TreeNode> stack = new LinkedList<>();
        Deque<TreeNode> clonedStack = new LinkedList<>();
        TreeNode node = original;
        TreeNode cloneTarget = cloned;
        while (node != null || !stack.isEmpty()){
            if (node != null){
                if (node == target){
                    return cloneTarget;// 找到目标，返回
                }
                // 节点不空，走左子树
                stack.push(node);
                node = node.left;
                clonedStack.push(cloneTarget);
                cloneTarget = cloneTarget.left;
            }else {
                // 节点空了，进入右子树
                node = stack.pop();
                node = node.right;
                cloneTarget = clonedStack.pop();
                cloneTarget = cloneTarget.right;
            }
        }
        return null;
    }
}

层次遍历代码

class Solution {
    public final TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target) {
        Queue<TreeNode> queue = new LinkedList<>();
        Queue<TreeNode> clonedQueue = new LinkedList<>();
        queue.offer(original);
        clonedQueue.offer(cloned);
        TreeNode node1;
        TreeNode node2;
        while (!queue.isEmpty()){
            node1 = queue.poll();
            node2 = clonedQueue.poll();
            if (target == node1){
                return node2;
            }
            if (node1.left != null){
                queue.offer(node1.left);
                clonedQueue.offer(node2.left);
            }
            if (node1.right != null){
                queue.offer(node1.right);
                clonedQueue.offer(node2.right);
            }
        }
        return null;
    }
}

统计信息

通过次数	提交次数	AC比率
10736	12801	83.9%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言