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

两棵一样的树，要在克隆树里返回哪个节点

给三样东西：原始树 original、它的副本克隆树 cloned，还有一个落在 original 里的目标节点 target。两棵树形状和值都一样，但节点是两套互相独立的对象，谁也不许改。要返回的，是克隆树里和 target 位置相同的那个节点——是位置对应，不是随便找个值相等的。题面例子：original=[1,2,3]、target 是值 3 那节点，返回克隆树根的右孩子 3。

只在克隆树里按值搜，遇到重复值会抓错人

克隆树里照着 target 的值去搜一个相同的数，题面这种值都不同的树似乎行——可进阶偏偏问：树里几个节点值都相等呢？按值搜会撞上第一个同值节点，它和 target 未必在同一位置，答案就错了。根子在于值相等不等于位置相同，只盯着值就把『位置对应』这个真正的要求丢了。

两棵树结构全同，那就让两个指针一起走

original 和 cloned 形状完全一样，那就别单独在克隆树翻找，而是让两个指针齐步走：一个在原树、一个在克隆树，永远停在同一位置。原树指针往左，克隆指针也往左；往右也同步。只需盯着原树指针，判断它是不是就是 target——判的是同一个对象，不是值相等——命中时克隆指针停的位置正好镜像对应，它指的就是答案。

递归函数每一步在比什么、返回什么

写成递归：函数带着原树指针 original 和克隆树指针 cloned 一起下探。先看 original 是不是空，空了返回空；再判 original 是不是 target 本身，是就返回当前的 cloned，即取克隆树对应位置的节点；都不满足，就先递归左边 original.left 和 cloned.left，没找到再递归右边。两边用『或』连：左子树返回非空就用它，否则看右子树，找到就层层传回。

[1,2,3] 找值 3、[7] 各怎么走

先看 [1,2,3]：根 1、左孩子 2、右孩子 3，target 是那个 3。进函数，original 是根 1，不是 target，递归左边。左边 original 是 2，也不是 target，左右孩子都空，递归返回空，左支落空。回到根看右边：original 是 3 就是 target 本身，返回克隆树的这个 3，它是根的右孩子，正是答案。

再看 [7]：整棵树只有根 7，target 就是它。进函数，original 不空，7 就是 target，返回克隆树的根，一步命中。

为什么是 O(n)，几处判定别写偏

复杂度：最坏把整棵原树扫一遍，每个节点只判一次，时间 O(n)，n 是节点数；提前命中就立刻返回。没有额外容器，只有递归栈，峰值深度等于树高 H：平衡树约 log n，链状退化时 H 等于 n，空间最坏 O(n)。

几处容易写偏：判定得比 original 是不是 target 本身，写成 original.val 等于 target.val 在有重复值的树里会误命中别的同值节点；命中后返回的必须是克隆树的 cloned，返回原树 target 就答成另一棵树；还有 original 为空的出口不能漏，少了它走到叶子外面就空指针出错。

Python

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)

C++

#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);
    }
};

Java

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);
    }
}