企业官网建设流程全解析

LeetCode 1379这题，我第一次见到时真把它当水题了——题目给出两棵二叉树，一棵是原始树，一棵是克隆树，外加一个指向原始树节点的target引用，要求返回克隆树中对应的那个节点。听起来无非就是遍历找节点，但实际动手写的时候，很多人包括当年的我，第一反应都是"去克隆树里找值等于target.val的节点不就行了"。这个思路在绝大多数测试样例上确实能跑通，可一旦树里出现重复值，就直接翻车。今天这篇把1379彻底拆开讲，内容包括同步遍历的底层逻辑、三种主流写法、重复值陷阱、以及从这题延伸出去的克隆二叉树、判等树、序列化重建等实战知识点，希望能帮你把"二叉树克隆与定位"这一系列问题一次吃透。适合正在刷二叉树专题、准备技术面试的读者，也适合想彻底搞懂"结构对应"和"值相等"区别的同学。

1. 原题拆解：三棵树的映射关系与题目真正想考的底层能力

1.1 题目输入到底在说什么

先回顾1379的完整输入。题目给了三个东西：original（原始二叉树根节点）、cloned（克隆二叉树根节点）、target（原始二叉树中某个节点的引用）。要求返回的是克隆二叉树中与target"对应的节点"。

很多同学第一次读题时会忽略一个关键前提：题目保证cloned是original的精确副本，也就是说两棵树的形状完全一样，每个对应位置上的节点值也一样。这里的"对应"指的是结构位置上的对应，而不是值相等。这个前提是整个题目的基石，后面所有解法都建立在这句话之上。

举个例子。原始树根节点值是1，左孩子是2，右孩子是3；克隆树也是完全相同的结构。target指向原始树中值为2的那个节点，那么答案就应该是克隆树中那个同样位于"根的左孩子"位置、值为2的节点。注意，关键的不是"值为2"，而是"根的左孩子"这个结构位置。只有把这两个维度分开，你才能真正理解这题。

1.2 为什么一致的结构就是解题的钥匙

正因为两棵树结构一致，我们才能用"同步遍历"的思路：同时从original和cloned的根出发，走完全相同的路径。在original这边，我们判断当前节点是不是target；在cloned这边，我们只是机械地跟着original走的每一步。当original的某一步走到了target，cloned自然也就走到了我们想要的答案。

打个比方，你在一张地图上标了一个点，手里拿着一张墨迹完全重合的复印地图。你要找的不是"同名地点"，因为地图上可能有两个同名地点；你要做的是从左上角开始，按完全相同的偏移量挪动手指，原图手指指到目标点时，复印图上同一位置的手指就是答案。这道题的target就是那个被标出来的点，cloned就是复印图。

这道题真正的考点有三层：第一，是否理解"结构对应"和"值相等"是两回事；第二，是否掌握在二叉树上同步携带两个指针进行遍历的能力；第三，是否能在递归、迭代之间灵活切换。第一层是新手最容易卡壳的地方，也是按值查找解法翻车的根源；第二层是核心实现能力；第三层是面试官最爱追问的延伸点。

1.3 为什么题目要同时给你两棵树

这里有个很值得琢磨的设计：题目为什么不只给cloned树和target的值？因为如果只给一棵克隆树和target的值，在节点值重复的场景下，你根本无法唯一确定该返回哪个节点。题目把original也给你，本质上就是在提示你：请利用原始树的节点引用做锚点，而不是依赖节点的值。

这也是这类"克隆题"的共同套路——给你的第二个结构永远是辅助定位用的，真正的判断逻辑永远放在第一个结构上。想通这一点，1379的解法方向基本就锁死了：你不需要在cloned里判断"哪个节点是答案"，你只需要在original里判断"我走到哪个节点了"。

2. 最稳的写法：DFS同步遍历的完整实现

2.1 递归同步遍历的核心代码

TreeNode就是LeetCode默认的二叉树节点定义，包含val、left、right三个字段，以下解法都基于这个结构。先上最推荐的写法，Python版本：

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

Java版本，逻辑完全一致，只是判等和判空的语法略有差异：

class Solution { public TreeNode getTargetCopy(TreeNode original, TreeNode cloned, TreeNode target) { if (original == null || original == target) { return cloned; } TreeNode left = getTargetCopy(original.left, cloned.left, target); if (left != null) { return left; } return getTargetCopy(original.right, cloned.right, target); } }

C++版本顺手也贴一下：

class Solution { public: TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target) { if (!original || original == target) return cloned; TreeNode* left = getTargetCopy(original->left, cloned->left, target); if (left) return left; return getTargetCopy(original->right, cloned->right, target); } };

三个语言版本虽然语法不同，但核心逻辑完全一致，可以用一句话概括：递归参数里同时携带original和cloned两个同位置的节点，original负责判断当前节点是否就是target，cloned则负责在命中时作为答案被返回。之所以强调"同时携带两个节点"，是因为我们不能先单独在original里找到target，再回到cloned里从头遍历一遍——那样既多花一次遍历，还得额外记录路径，完全没必要，也会让代码复杂得多。

2.2 为什么判断条件是"同一引用"而不是"值相等"

代码里用的是original is target（Python）或original == target（Java/C++），这在题目语义下都是引用比较。原因很简单：target是原始树中的某个真实节点对象，我们要找的是"同一个内存位置"的节点，而不是"值长得一样"的节点。只有引用相等，才能确保结构位置完全对应。

这里有一个容易被忽略的语言细节：在Python里，TreeNode类没有重写__eq__方法，所以==默认也是引用比较，写original == target也能跑通。但用is语义更明确，因为is在Python里就是纯粹的引用标识比较，完全不会触发任何潜在的相等逻辑。Java和C++里，引用类型的==本身就是比较引用地址，没有问题。

有些同学会问：那我用original.val == target.val行不行？后面会专门讲为什么不行，这里先记住结论：判断必须用引用相等，值相等会导致重复值场景下的错位，而这个错位是隐藏用例最容易埋的点。

2.3 递归执行过程的逐步走查

光看代码可能还是有点抽象，举个具体例子走一遍。假设原始树长这样：

1 / \ 2 3 / \ 4 5

target指向值为5的节点，也就是根的左孩子的右孩子。调用递归函数后，过程是这样的：

第一步，进入getTargetCopy(original=1, cloned=1', target=5节点)。original不是空，也不是target，继续。

第二步，进入左分支getTargetCopy(original=2, cloned=2', target)。original=2不是target，继续。

第三步，进入左分支getTargetCopy(original=4, cloned=4', target)。original=4不是target，左右孩子都为空，返回null。回到original=2的这次调用，left为null，于是进入右分支。

第四步，进入右分支getTargetCopy(original=5, cloned=5', target)。此时original is target成立，直接返回cloned=5'。

第五步，回到original=2的这次调用，left不为空，把5'继续向上返回。回到根的调用，同样直接返回5'。最终得到克隆树中对应位置的节点。

整个过程可以看到，cloned节点根本没参与任何"找"的逻辑，它只是被同步地带上了。真正决定走向的是original，cloned只是复制了original的每一步移动。这种"一个指针做主、一个指针跟随"的模式，在后面克隆整棵树的场景里会以镜像形式再次出现。

2.4 复杂度分析与三处边界条件

时间复杂度O(n)，因为最坏情况下要遍历整棵树才能定位到target。空间复杂度O(h)，h是树高，由递归栈深度决定，最坏情况是链状树的O(n)，平衡二叉树是O(logn)。

边界条件有三个需要重点注意。第一，original为空时，cloned也一定为空，此时返回null即可。这个空判断必须写在引用判断之前，否则访问空节点的val或left会直接抛异常。第二，target就是根节点时，第一次调用直接命中，返回cloned根节点，这是最快命中路径，代码天然支持。第三，题目虽然保证original非空，但作为通用解法，空判断不能省，因为你无法预料本地调试时会不会传一个空树进去。

3. 常见错误与陷阱：为什么不能只按值查找

3.1 错误解法的典型代码与翻车现场

最常见的错误解法，是忽略original，直接在cloned树上做普通DFS按值查找，长这样：

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

注意观察，这个写法里original参数从头到尾没有被使用过，递归完全只在cloned树上基于值来搜索。这类写法在刷题网站的简单示例上大概率能通过，因为示例里的节点值往往是唯一设计的，按值找和按位置找的结果恰好一样。

但一旦树里出现重复值，问题就来了。我见过很多人在讨论区里贴这种代码，然后困惑地问"为什么我本地跑通了，提交却错误"。原因很简单：本地示例为了可读性通常使用唯一值，而后台隐藏用例会专门构造重复值来验证你对题目语义的理解。

3.2 重复值场景的完整反例

构造一个反例，原始树如下，克隆树结构完全一致：

1 / \ 2 2 / \ 3 4

target指向原始树中"根的右孩子"，也就是值为2的那个节点。这是合法的输入，树的右孩子存在，target指向它。按正确解法，答案应该是克隆树中右孩子位置的节点。

但如果用按值查找，在克隆树中先遇到的是"根的左孩子"，它的值也是2，于是函数错误地返回了左孩子节点。两个节点值相同，但结构位置完全不同，返回左孩子就是错的。这个反例直接击穿了所有"按值查找"的解法。

你可能觉得这只是极端情况，但普通二叉树本来就不要求节点值唯一，值重复是再正常不过的事。后台测试用例专门有这类重复值数据，就是为了卡掉按值查找的思路。如果你只按值查找，提交之后大概率会挂在某个隐藏用例上，而且报错信息只告诉你"返回了错误的节点"，不会告诉你具体是哪个值重复了，排查起来相当难受。

3.3 其他容易忽略的三个实现细节

除了按值查找，还有三个细节值得单独拎出来说。

第一，只遍历克隆树而不看原始树，这在逻辑上已经违背了题目描述的映射关系。如果将来题目变形，比如额外给出target在原始树中的父节点信息，要求你利用路径定位，按值查找的解法会直接失效。所以不要养成"能用值凑就凑"的坏习惯。

第二，忘记处理空节点。写递归时，先判断当前节点是否为空，再判断引用是否相等，顺序不能反。Java和C++里尤其要注意，空指针解引用是编译能过、运行崩溃的典型问题，而且崩溃栈往往只指向库函数内部，定位起来很费时间。

第三，递归函数的返回值类型是TreeNode，不是int也不是boolean。有些同学写着写着把递归函数当成"判断target是否在这棵子树下"的布尔函数，最后返回了个布尔值，连编译都过不了。要时刻记住这个函数的语义是：从当前位置出发，返回克隆树中与target对应位置的节点；找不到就返回null。

4. 迭代写法与实战延伸：从找节点到克隆整棵树

4.1 显式栈迭代DFS实现

递归虽然简洁，但很多面试官会要求写迭代版本，顺便考察你对递归栈溢出风险的理解。用显式栈模拟系统调用栈，每次压栈都同时压入original和cloned的成对节点：

class Solution: def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode: stack = [(original, cloned)] while stack: o, c = stack.pop() if o is target: return c if o.left: stack.append((o.left, c.left)) if o.right: stack.append((o.right, c.right)) return None

逻辑很简单：先检查当前这一对节点，如果original这边不是target，就把左右孩子成对压入栈。由于栈是后进先出，实际遍历顺序和压栈顺序有关，但这不重要，因为我们要找的是确定节点，任何遍历顺序都能找到，只要保证同步携带克隆节点即可。

Java的迭代版本写法类似，注意用Deque而不是Stack，性能更好：

class Solution { public TreeNode getTargetCopy(TreeNode original, TreeNode cloned, TreeNode target) { Deque<TreeNode[]> stack = new ArrayDeque<>(); stack.push(new TreeNode[]{original, cloned}); while (!stack.isEmpty()) { TreeNode[] cur = stack.pop(); if (cur[0] == target) return cur[1]; if (cur[0].left != null) stack.push(new TreeNode[]{cur[0].left, cur[1].left}); if (cur[0].right != null) stack.push(new TreeNode[]{cur[0].right, cur[1].right}); } return null; } }

4.2 BFS队列实现与三种写法对比

还可以用队列做层序遍历，每一层从左到右同步推进，代码几乎只是把栈换成队列：

from collections import deque class Solution: def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode: queue = deque([(original, cloned)]) while queue: o, c = queue.popleft() if o is target: return c if o.left: queue.append((o.left, c.left)) if o.right: queue.append((o.right, c.right)) return None

三种写法的对比如下。递归DFS用的是系统调用栈，额外空间是O(h)；迭代DFS用显式栈，空间也是O(h)，但避免了深树时的栈溢出；BFS用队列，空间是O(w)，w为树的最大宽度。三者时间复杂度都是O(n)，只是常数和空间特征不同。

4.3 延伸一：完整克隆一棵二叉树的递归实现

1379直接给了克隆树，但实际工作中如果让你自己克隆一棵二叉树，核心做法是同步新建节点：

def clone_tree(root): if not root: return None new_root = TreeNode(root.val) new_root.left = clone_tree(root.left) new_root.right = clone_tree(root.right) return new_root

这段代码可以看作1379的前置知识。克隆树本质上是对原始树做了一次前序遍历，每个节点都复制一份。理解了这个过程，你就明白为什么original和cloned在结构上严格对应——因为克隆本身就是一次同步遍历。

反过来看1379，它其实是在克隆过程中加了一个标记动作：克隆函数本来在遍历到每个节点时都会new一个新节点，而1379的任务是当遍历到target时，不新建节点，而是把当前已经建好的克隆节点返回。这个视角非常有用。把"克隆过程"和"查找过程"放在一起看，你会发现它们完全共享同一套同步遍历骨架：克隆是"每步都建节点"，查找是"只关心目标节点，其余路径原样跟随"。

4.4 延伸二：判等树与序列化重建，三条知识线串成一张网

顺着"结构对应"这个思路，还能串起一系列相关题目。判断两棵二叉树是否相同的LeetCode第100题，代码和1379简直像镜像版本：

def is_same_tree(p, q): if not p and not q: return True if not p or not q: return False if p.val != q.val: return False return is_same_tree(p.left, q.left) and is_same_tree(p.right, q.right)

1379是"已知两棵树相同，找对应位置的节点"，100是"判断两棵树是否相同"。一个在确认相同的树上做定位，一个在验证是否真的相同，两者共享同一个骨架：同步遍历两棵树、成对访问节点。唯一差异是判断条件：一个用引用相等判断"该返回了"，一个用值不相等判断"该返回false了"。

再往深处走，二叉树的序列化与反序列化（LeetCode 297）也用到同样的思想。序列化是把树变成字符串，反序列化是按同样的遍历顺序把字符串重建为树，重建过程中的同步遍历本质上就是克隆的逆过程。理解1379，相当于拿到了理解这些进阶题的一块重要跳板。刷题最忌讳一道一道孤立地刷，把这些"长得不一样但内核相同"的题目放一起对比，你会发现很多题目其实是在反复练习同一个基本功：结构上的同步遍历。

5. 同类题对比与面试复盘：一道题带出一类题

5.1 如何快速识别"克隆+定位"类题目

刷题量上来之后你会发现，很多题目都是有信号词的。看到clone、copy、same node、corresponding node这类关键词，第一反应就应该是"同步遍历两棵树或两张图"。1379就是这类题目的典型代表。

识别出这个模式之后，解题框架非常固定：定义成对遍历的递归函数，一个指针走原始结构，一个指针走克隆结构，原始结构的指针负责判断位置，克隆结构的指针负责输出答案。判断用引用相等，不用值相等，这是整个框架里最容易错的一环。把这个模式记熟，所有带"克隆"标签的二叉树题，你至少能秒出同步遍历这一版解法。

5.2 与Clone Graph等题目的横向对比

LeetCode第133题克隆图是另一道经典克隆题，经常和1379一起出现在"克隆系列"的讨论里。图的结构比二叉树复杂，因为可能存在环、每个节点有多个邻居，所以克隆图必须用哈希表维护"原节点到新节点的映射"，防止死循环。而二叉树没有环，父子关系天然单向，所以克隆二叉树完全可以不用哈希表，直接按递归位置同步走。

对比一下两题的解法要点，理解会更加清晰：

如果在面试中同时被问到这两题，你可以主动点出这层对比，面试官会觉得你确实理解了解法的底层动因，而不只是背了代码。这个对比也说明一个道理：数据结构越简单，解法里的辅助结构越少；数据结构变复杂时，第一反应应该是引入哈希表来记录对应关系。

5.3 给面试者的三句话表达模板

这类代码很短的小题，面试考察的重点反而不是代码本身，而是你解释思路的能力。我建议按三步来表述。

第一句，点明核心策略："我采用同步遍历，同时从original和cloned的根节点出发，每次走相同的左或右分支，始终维护一对结构位置相同的节点。"

第二句，说明终止条件："当original这边走到target时，说明位置已经锁定，此时cloned这边对应的节点就是答案。"

第三句，解释边界与复杂度："original为空时cloned也为空，返回null。时间复杂度O(n)，空间复杂度O(h)，h是树高。"

这三句话说完，已经覆盖了算法思想、终止条件和复杂度三个维度。如果面试官追问能不能不用递归，再把4.1里的迭代版写出来。注意不要把递归写法里的剪枝说得太神秘，其实就是"左子树找到了就返回，找不到再找右子树"，一句话带过即可。

最后分享一个我复盘时想通的点：把1379、100（相同的树）、297（序列化与反序列化）、133（克隆图）放在一起刷，你会发现它们的共同底层能力都是对结构进行同步遍历。二叉树题目千变万化，但很多看似花哨的题，拆到底都是遍历加位置映射这两个基本功。1379是练习这个基本功性价比很高的一题，代码量不大，坑却不少，值得多写几遍，直到闭着眼都能把递归版和迭代版都写对。

我个人在实际刷题中的体会是，这题最好的练法不是直接看题解，而是先故意写出"按值查找"的错误版本，再用一个构造好的重复值样例去跑，亲眼看着它返回错误节点。这个过程会让你对"引用对应"和"值相等"的区别产生肌肉记忆。之后再写同步遍历版本，你甚至能预判到测试用例会怎么卡你。刷题嘛，不怕踩坑，怕的是不知道坑在哪儿。