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

记牢一句: 两个指针齐步走,一个在原树、一个在克隆树,永远同位置。原树指针踩中目标的那一刻,克隆树指针停的位置就是答案。下面每一帧都在套这条规则。

总览 · 两棵一样的树：先看清布局。屏幕主舞台画的是原始树: 根是 50,左孩子是 30,右孩子是 80;30 下面挂着 20 和 40,40 再往下挂着一个 45;80 下面挂着 70 和 90。克隆树形状和这棵完全一样、每个值也一样,只是另一套独立的节点。高亮的这个 70,就是原始树里的目标节点。我们的任务,是在克隆树里把和它位置对应的那个节点找出来。

副本 · 两套独立节点：强调一个容易绕晕的点: 原始树和克隆树虽然长得一模一样、每个位置的值都相等,但它们是两套各自独立的节点。题目要的不是「值等于 70」这么简单,而是「克隆树里和原始树这个 70 处在同一位置」的那个节点。所以光在克隆树里搜一个值 70 不够稳,正经做法是带着两棵树一起走,用位置来对应。

方法 · 两个指针齐步走：具体怎么走。准备两个指针: op 在原始树上,cp 在克隆树上,一开始都指向各自的根。接下来每一步,两个指针都朝同一个方向同步移动,先试左孩子、再试右孩子。因为两棵树形状一样,它俩的脚步永远齐。我们只盯着原树这边的 op: 它什么时候踩中目标,克隆树那边的 cp 就同时停在了对应位置。现在两个指针都在根上,开始。

到根 · op 与 cp 同指根：两个指针都落在各自的根上: op 指着原始树的根 50,cp 指着克隆树的根。注意它俩是同一个位置。每到一个新位置,第一件事永远是问: 原树这边的 op,是不是就是目标那个节点 70?来看根这边。

判定 · 根 50 不是目标：原树根是 50,目标是那个 70,显然这个根不是目标节点。既然不是,就让两个指针同步往下: 先走左孩子。op 从原树的 50 走到它的左孩子 30,cp 在克隆树里同步走到对应的左孩子。它俩还是停在同一位置。

到 30 · 两指针同步下移：两个指针同步落到了下一层左边这个位置,原树这边 op 指着 30。根 50 现在标成路径色,表示它在当前这条往下的路径上、已经看过。老规矩,先问: 这个 30 是不是目标节点 70?

判定 · 30 不是目标：30 不是目标 70。那就继续往下,两个指针同步走 30 的左孩子。op 从原树的 30 走到它的左孩子 20,cp 在克隆树同步走到对应位置。先把这一支探到底。

到 20 · 左下角的叶子：两指针同步落到 20。30 也进入路径色。这个 20 是个叶子节点,下面没有孩子了。还是先判: 它是不是目标 70?

判定 · 20 不是, 叶子回退：20 不是 70,而且它是叶子,左右都没有孩子可以再往下走,这一支到底了。于是两个指针一起回退,退回到 30,准备改试 30 还没走过的右孩子。被否定的 20 标成已访问色。

到 40 · 30 的右孩子：两个指针同步走到 30 的右孩子,原树这边 op 指着 40。判: 这个 40 是不是目标 70?

判定 · 40 不是目标：40 也不是 70。继续往下,两指针同步走 40 的左孩子。op 从原树的 40 走到它的左孩子 45,cp 在克隆树同步跟上。

到 45 · 40 的左孩子叶子：两个指针落到 45,40 进入路径色。这个 45 又是一个叶子。判: 它是不是目标 70?

判定 · 45 不是, 回退：45 不是 70,它也是叶子。回退到 40,40 的右孩子是空,没得走了。再回退到 30,30 的左孩子 20、右孩子 40 这两支都走完了,整个以 30 为根的左子树彻底没有找到目标。两个指针一起退回更上面。

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

到 80 · 50 的右孩子：两个指针同步走到根的右孩子,原树这边 op 指着 80。判: 这个 80 是不是目标 70?

判定 · 80 不是目标：80 不是 70。继续往下,两指针同步走 80 的左孩子。op 从原树的 80 走到它的左孩子,cp 在克隆树同步跟上。下一帧就是关键。

到 70 · 80 的左孩子：两个指针同步落到了 80 的左孩子。原树这边 op 指着 70。这个位置看起来很关键,因为目标正是原始树里那个 70。来做最后一次判定: op 是不是就是目标节点?

命中 · op 踩中目标：op 现在指的,正是原始树里那个目标节点 70,它就是 target 本身。命中了!按规则,这一刻不用再往下走,直接看克隆树这边: 因为两个指针一路齐步走,cp 此刻停的位置,正好和 op 镜像对应。答案就在克隆树的这个位置上。

对应 · 克隆指针指向克隆 70：把镜头切到克隆树这边。原树的 op 落在 80 的左孩子这个位置上命中目标,那么克隆树的 cp,此刻同样停在克隆树 80 的左孩子这个位置。这个位置上的节点,值也是 70,但它是克隆树里那个独立的节点。它就是我们要返回的答案。

答案 · 返回克隆树的这个节点：把答案节点标成绿色。注意,我们返回的是克隆树里这个节点的引用,不是原始树里的那个目标。两者值都是 70,可身份不同,题目要的是克隆树这一个。定位它靠的不是去克隆树里搜值 70,而是带着两棵树一路同步走、用位置把它锁定。

回放 · 原树定位 + 克隆树取节点：回放整个过程。我们没有单独去克隆树里翻找,而是让两个指针在两棵树上齐步走: 原树这边沿着 50、右孩子 80、再到左孩子,踩中了目标 70;克隆树那边同步走到了一模一样的位置。位置一对应,克隆树那个位置上的节点就是答案。这就是用同步遍历把位置对上的妙处。

完成 · 答案锁定：收工。绿色这个节点,代表的是克隆树里和原始树目标同一位置的那个 70,它就是我们要返回的引用。整道题的核心,就是两棵同形的树一起递归: 原树指针找到目标的瞬间,克隆树指针自然停在了对应位置上。

边界看三种: 单节点树根即答案;目标在右孩子要先探左再回退;目标是根时第一步就命中返回克隆根。

面试重点: 进阶重复值靠按身份比较加同步遍历仍成立;可改双队列 BFS;空间 O(H) 来自递归栈峰值,链状退化到 O(n)。