找出克隆二叉树中的相同节点 图解题解

这道题到底在问什么

输入

original=[7], target 指向那个 7

输出

克隆树的根 7(整棵树只有一个节点)

输入

original=[1,2,3], target 指向值 3 的节点

输出

克隆树里根的右孩子 3(位置对应)

先想最直接的笨办法

两个指针退回到了根 50。回顾一下,原树根 50 的整个左子树: 30、20、40、45,挨个看过,没有一个是目标 70。按先左后右的顺序,左边找完了,现在轮到根的右子树。两指针一起转向右孩子。（动画第 17 步）

最优解：一步一步想明白

1. 3记牢一句: 两个指针齐步走,一个在原树、一个在克隆树,永远同位置。原树指针踩中目标的那一刻,克隆树指针停的位置就是答案。下面每一帧都在套这条规则。
2. 4原树与克隆树同形同值,目标是原树里的 70先看清布局。屏幕主舞台画的是原始树: 根是 50,左孩子是 30,右孩子是 80;30 下面挂着 20 和 40,40 再往下挂着一个 45;80 下面挂着 70 和 90。克隆树形状和这棵完全一样、每个值也一样,只是另一套独立的节点。高亮的这个 70,就是原始树里的目标节点。我们的任务,是在克隆树里把和它位置对应的那个节点找出来。
3. 5形状值全同,但原树克隆树是两套对象强调一个容易绕晕的点: 原始树和克隆树虽然长得一模一样、每个位置的值都相等,但它们是两套各自独立的节点。题目要的不是「值等于 70」这么简单,而是「克隆树里和原始树这个 70 处在同一位置」的那个节点。所以光在克隆树里搜一个值 70 不够稳,正经做法是带着两棵树一起走,用位置来对应。
4. 6op 在原树, cp 在克隆树, 永远同位置具体怎么走。准备两个指针: op 在原始树上,cp 在克隆树上,一开始都指向各自的根。接下来每一步,两个指针都朝同一个方向同步移动,先试左孩子、再试右孩子。因为两棵树形状一样,它俩的脚步永远齐。我们只盯着原树这边的 op: 它什么时候踩中目标,克隆树那边的 cp 就同时停在了对应位置。现在两个指针都在根上,开始。
5. 7op 指原树根 50, cp 指克隆树根两个指针都落在各自的根上: op 指着原始树的根 50,cp 指着克隆树的根。注意它俩是同一个位置。每到一个新位置,第一件事永远是问: 原树这边的 op,是不是就是目标那个节点 70?来看根这边。
6. 850 不是目标 70, 两指针同步进左子树原树根是 50,目标是那个 70,显然这个根不是目标节点。既然不是,就让两个指针同步往下: 先走左孩子。op 从原树的 50 走到它的左孩子 30,cp 在克隆树里同步走到对应的左孩子。它俩还是停在同一位置。
7. 9op 到原树的 30, cp 到克隆树同位置两个指针同步落到了下一层左边这个位置,原树这边 op 指着 30。根 50 现在标成路径色,表示它在当前这条往下的路径上、已经看过。老规矩,先问: 这个 30 是不是目标节点 70?
8. 1030 不是 70, 继续同步进左孩子30 不是目标 70。那就继续往下,两个指针同步走 30 的左孩子。op 从原树的 30 走到它的左孩子 20,cp 在克隆树同步走到对应位置。先把这一支探到底。
9. 11op 到原树的 20(叶子), cp 同位置两指针同步落到 20。30 也进入路径色。这个 20 是个叶子节点,下面没有孩子了。还是先判: 它是不是目标 70?
10. 1220 不是 70 且无孩子, 退回 30 试右20 不是 70,而且它是叶子,左右都没有孩子可以再往下走,这一支到底了。于是两个指针一起回退,退回到 30,准备改试 30 还没走过的右孩子。被否定的 20 标成已访问色。
11. 13op 到原树的 40, cp 同位置两个指针同步走到 30 的右孩子,原树这边 op 指着 40。判: 这个 40 是不是目标 70?
12. 1440 不是 70, 同步进 40 的左孩子40 也不是 70。继续往下,两指针同步走 40 的左孩子。op 从原树的 40 走到它的左孩子 45,cp 在克隆树同步跟上。
13. 15op 到原树的 45(叶子), cp 同位置两个指针落到 45,40 进入路径色。这个 45 又是一个叶子。判: 它是不是目标 70?
14. 1645 不是, 40 右空, 30 两支走完45 不是 70,它也是叶子。回退到 40,40 的右孩子是空,没得走了。再回退到 30,30 的左孩子 20、右孩子 40 这两支都走完了,整个以 30 为根的左子树彻底没有找到目标。两个指针一起退回更上面。
15. 17原树整个左子树走完没找到, 退回根两个指针退回到了根 50。回顾一下,原树根 50 的整个左子树: 30、20、40、45,挨个看过,没有一个是目标 70。按先左后右的顺序,左边找完了,现在轮到根的右子树。两指针一起转向右孩子。
16. 18op 到原树的 80, cp 同位置两个指针同步走到根的右孩子,原树这边 op 指着 80。判: 这个 80 是不是目标 70?
17. 1980 不是 70, 同步进 80 的左孩子80 不是 70。继续往下,两指针同步走 80 的左孩子。op 从原树的 80 走到它的左孩子,cp 在克隆树同步跟上。下一帧就是关键。
18. 20op 到原树的 70, cp 到克隆树同位置两个指针同步落到了 80 的左孩子。原树这边 op 指着 70。这个位置看起来很关键,因为目标正是原始树里那个 70。来做最后一次判定: op 是不是就是目标节点?
19. 21原树 op 正是目标节点 70op 现在指的,正是原始树里那个目标节点 70,它就是 target 本身。命中了!按规则,这一刻不用再往下走,直接看克隆树这边: 因为两个指针一路齐步走,cp 此刻停的位置,正好和 op 镜像对应。答案就在克隆树的这个位置上。
20. 22cp 停在克隆树同一位置, 即答案把镜头切到克隆树这边。原树的 op 落在 80 的左孩子这个位置上命中目标,那么克隆树的 cp,此刻同样停在克隆树 80 的左孩子这个位置。这个位置上的节点,值也是 70,但它是克隆树里那个独立的节点。它就是我们要返回的答案。
21. 23返回 cp 指向的克隆 70把答案节点标成绿色。注意,我们返回的是克隆树里这个节点的引用,不是原始树里的那个目标。两者值都是 70,可身份不同,题目要的是克隆树这一个。定位它靠的不是去克隆树里搜值 70,而是带着两棵树一路同步走、用位置把它锁定。
22. 24一路同步走, 位置一对应即得答案回放整个过程。我们没有单独去克隆树里翻找,而是让两个指针在两棵树上齐步走: 原树这边沿着 50、右孩子 80、再到左孩子,踩中了目标 70;克隆树那边同步走到了一模一样的位置。位置一对应,克隆树那个位置上的节点就是答案。这就是用同步遍历把位置对上的妙处。
23. 25返回克隆树 80 的左孩子那个 70收工。绿色这个节点,代表的是克隆树里和原始树目标同一位置的那个 70,它就是我们要返回的引用。整道题的核心,就是两棵同形的树一起递归: 原树指针找到目标的瞬间,克隆树指针自然停在了对应位置上。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
        if original is None:
            return None
        if original is target:
            return cloned
        return self.getTargetCopy(original.left, cloned.left, target) or self.getTargetCopy(original.right, cloned.right, target)

#include <iostream>
#include <optional>
#include <queue>
#include <vector>
using namespace std;
struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x): val(x), left(nullptr), right(nullptr) {} };
class Solution {
public:
    TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target) {
        if (!original) return nullptr;
        if (original == target) return cloned;
        auto left = getTargetCopy(original->left, cloned->left, target);
        return left ? left : getTargetCopy(original->right, cloned->right, target);
    }
};

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);
        return left != null ? left : getTargetCopy(original.right, cloned.right, target);
    }
}

复杂度

面试官可能追问