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的某一步走到了targetcloned自然也就走到了我们想要的答案。打个比方你在一张地图上标了一个点手里拿着一张墨迹完全重合的复印地图。你要找的不是同名地点因为地图上可能有两个同名地点你要做的是从左上角开始按完全相同的偏移量挪动手指原图手指指到目标点时复印图上同一位置的手指就是答案。这道题的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负责判断当前节点是否就是targetcloned则负责在命中时作为答案被返回。之所以强调同时携带两个节点是因为我们不能先单独在original里找到target再回到cloned里从头遍历一遍——那样既多花一次遍历还得额外记录路径完全没必要也会让代码复杂得多。2.2 为什么判断条件是同一引用而不是值相等代码里用的是original is targetPython或original targetJava/C这在题目语义下都是引用比较。原因很简单target是原始树中的某个真实节点对象我们要找的是同一个内存位置的节点而不是值长得一样的节点。只有引用相等才能确保结构位置完全对应。这里有一个容易被忽略的语言细节在Python里TreeNode类没有重写__eq__方法所以默认也是引用比较写original target也能跑通。但用is语义更明确因为is在Python里就是纯粹的引用标识比较完全不会触发任何潜在的相等逻辑。Java和C里引用类型的本身就是比较引用地址没有问题。有些同学会问那我用original.val target.val行不行后面会专门讲为什么不行这里先记住结论判断必须用引用相等值相等会导致重复值场景下的错位而这个错位是隐藏用例最容易埋的点。2.3 递归执行过程的逐步走查光看代码可能还是有点抽象举个具体例子走一遍。假设原始树长这样1 / \ 2 3 / \ 4 5target指向值为5的节点也就是根的左孩子的右孩子。调用递归函数后过程是这样的第一步进入getTargetCopy(original1, cloned1, target5节点)。original不是空也不是target继续。第二步进入左分支getTargetCopy(original2, cloned2, target)。original2不是target继续。第三步进入左分支getTargetCopy(original4, cloned4, target)。original4不是target左右孩子都为空返回null。回到original2的这次调用left为null于是进入右分支。第四步进入右分支getTargetCopy(original5, cloned5, target)。此时original is target成立直接返回cloned5。第五步回到original2的这次调用left不为空把5继续向上返回。回到根的调用同样直接返回5。最终得到克隆树中对应位置的节点。整个过程可以看到cloned节点根本没参与任何找的逻辑它只是被同步地带上了。真正决定走向的是originalcloned只是复制了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 4target指向原始树中根的右孩子也就是值为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) { DequeTreeNode[] 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)只是常数和空间特征不同。写法遍历顺序额外空间使用场景递归DFS前序O(h)h为树高代码最简洁面试优先写迭代DFS前序或后序取决于压栈顺序O(h)树很深时避免递归栈溢出BFS层序O(w)w为最大宽度需要按层定位时使用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一起出现在克隆系列的讨论里。图的结构比二叉树复杂因为可能存在环、每个节点有多个邻居所以克隆图必须用哈希表维护原节点到新节点的映射防止死循环。而二叉树没有环父子关系天然单向所以克隆二叉树完全可以不用哈希表直接按递归位置同步走。对比一下两题的解法要点理解会更加清晰题目数据结构是否需要哈希表核心难点1379 找克隆二叉树节点二叉树不需要同步遍历区分引用与值133 克隆图图可能有环需要用映射防止重复克隆和死循环如果在面试中同时被问到这两题你可以主动点出这层对比面试官会觉得你确实理解了解法的底层动因而不只是背了代码。这个对比也说明一个道理数据结构越简单解法里的辅助结构越少数据结构变复杂时第一反应应该是引入哈希表来记录对应关系。5.3 给面试者的三句话表达模板这类代码很短的小题面试考察的重点反而不是代码本身而是你解释思路的能力。我建议按三步来表述。第一句点明核心策略我采用同步遍历同时从original和cloned的根节点出发每次走相同的左或右分支始终维护一对结构位置相同的节点。第二句说明终止条件当original这边走到target时说明位置已经锁定此时cloned这边对应的节点就是答案。第三句解释边界与复杂度original为空时cloned也为空返回null。时间复杂度O(n)空间复杂度O(h)h是树高。这三句话说完已经覆盖了算法思想、终止条件和复杂度三个维度。如果面试官追问能不能不用递归再把4.1里的迭代版写出来。注意不要把递归写法里的剪枝说得太神秘其实就是左子树找到了就返回找不到再找右子树一句话带过即可。最后分享一个我复盘时想通的点把1379、100相同的树、297序列化与反序列化、133克隆图放在一起刷你会发现它们的共同底层能力都是对结构进行同步遍历。二叉树题目千变万化但很多看似花哨的题拆到底都是遍历加位置映射这两个基本功。1379是练习这个基本功性价比很高的一题代码量不大坑却不少值得多写几遍直到闭着眼都能把递归版和迭代版都写对。我个人在实际刷题中的体会是这题最好的练法不是直接看题解而是先故意写出按值查找的错误版本再用一个构造好的重复值样例去跑亲眼看着它返回错误节点。这个过程会让你对引用对应和值相等的区别产生肌肉记忆。之后再写同步遍历版本你甚至能预判到测试用例会怎么卡你。刷题嘛不怕踩坑怕的是不知道坑在哪儿。 LeetCode 1379详解：二叉树同步遍历与克隆节点定位的陷阱与解法
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的某一步走到了targetcloned自然也就走到了我们想要的答案。打个比方你在一张地图上标了一个点手里拿着一张墨迹完全重合的复印地图。你要找的不是同名地点因为地图上可能有两个同名地点你要做的是从左上角开始按完全相同的偏移量挪动手指原图手指指到目标点时复印图上同一位置的手指就是答案。这道题的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负责判断当前节点是否就是targetcloned则负责在命中时作为答案被返回。之所以强调同时携带两个节点是因为我们不能先单独在original里找到target再回到cloned里从头遍历一遍——那样既多花一次遍历还得额外记录路径完全没必要也会让代码复杂得多。2.2 为什么判断条件是同一引用而不是值相等代码里用的是original is targetPython或original targetJava/C这在题目语义下都是引用比较。原因很简单target是原始树中的某个真实节点对象我们要找的是同一个内存位置的节点而不是值长得一样的节点。只有引用相等才能确保结构位置完全对应。这里有一个容易被忽略的语言细节在Python里TreeNode类没有重写__eq__方法所以默认也是引用比较写original target也能跑通。但用is语义更明确因为is在Python里就是纯粹的引用标识比较完全不会触发任何潜在的相等逻辑。Java和C里引用类型的本身就是比较引用地址没有问题。有些同学会问那我用original.val target.val行不行后面会专门讲为什么不行这里先记住结论判断必须用引用相等值相等会导致重复值场景下的错位而这个错位是隐藏用例最容易埋的点。2.3 递归执行过程的逐步走查光看代码可能还是有点抽象举个具体例子走一遍。假设原始树长这样1 / \ 2 3 / \ 4 5target指向值为5的节点也就是根的左孩子的右孩子。调用递归函数后过程是这样的第一步进入getTargetCopy(original1, cloned1, target5节点)。original不是空也不是target继续。第二步进入左分支getTargetCopy(original2, cloned2, target)。original2不是target继续。第三步进入左分支getTargetCopy(original4, cloned4, target)。original4不是target左右孩子都为空返回null。回到original2的这次调用left为null于是进入右分支。第四步进入右分支getTargetCopy(original5, cloned5, target)。此时original is target成立直接返回cloned5。第五步回到original2的这次调用left不为空把5继续向上返回。回到根的调用同样直接返回5。最终得到克隆树中对应位置的节点。整个过程可以看到cloned节点根本没参与任何找的逻辑它只是被同步地带上了。真正决定走向的是originalcloned只是复制了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 4target指向原始树中根的右孩子也就是值为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) { DequeTreeNode[] 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)只是常数和空间特征不同。写法遍历顺序额外空间使用场景递归DFS前序O(h)h为树高代码最简洁面试优先写迭代DFS前序或后序取决于压栈顺序O(h)树很深时避免递归栈溢出BFS层序O(w)w为最大宽度需要按层定位时使用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一起出现在克隆系列的讨论里。图的结构比二叉树复杂因为可能存在环、每个节点有多个邻居所以克隆图必须用哈希表维护原节点到新节点的映射防止死循环。而二叉树没有环父子关系天然单向所以克隆二叉树完全可以不用哈希表直接按递归位置同步走。对比一下两题的解法要点理解会更加清晰题目数据结构是否需要哈希表核心难点1379 找克隆二叉树节点二叉树不需要同步遍历区分引用与值133 克隆图图可能有环需要用映射防止重复克隆和死循环如果在面试中同时被问到这两题你可以主动点出这层对比面试官会觉得你确实理解了解法的底层动因而不只是背了代码。这个对比也说明一个道理数据结构越简单解法里的辅助结构越少数据结构变复杂时第一反应应该是引入哈希表来记录对应关系。5.3 给面试者的三句话表达模板这类代码很短的小题面试考察的重点反而不是代码本身而是你解释思路的能力。我建议按三步来表述。第一句点明核心策略我采用同步遍历同时从original和cloned的根节点出发每次走相同的左或右分支始终维护一对结构位置相同的节点。第二句说明终止条件当original这边走到target时说明位置已经锁定此时cloned这边对应的节点就是答案。第三句解释边界与复杂度original为空时cloned也为空返回null。时间复杂度O(n)空间复杂度O(h)h是树高。这三句话说完已经覆盖了算法思想、终止条件和复杂度三个维度。如果面试官追问能不能不用递归再把4.1里的迭代版写出来。注意不要把递归写法里的剪枝说得太神秘其实就是左子树找到了就返回找不到再找右子树一句话带过即可。最后分享一个我复盘时想通的点把1379、100相同的树、297序列化与反序列化、133克隆图放在一起刷你会发现它们的共同底层能力都是对结构进行同步遍历。二叉树题目千变万化但很多看似花哨的题拆到底都是遍历加位置映射这两个基本功。1379是练习这个基本功性价比很高的一题代码量不大坑却不少值得多写几遍直到闭着眼都能把递归版和迭代版都写对。我个人在实际刷题中的体会是这题最好的练法不是直接看题解而是先故意写出按值查找的错误版本再用一个构造好的重复值样例去跑亲眼看着它返回错误节点。这个过程会让你对引用对应和值相等的区别产生肌肉记忆。之后再写同步遍历版本你甚至能预判到测试用例会怎么卡你。刷题嘛不怕踩坑怕的是不知道坑在哪儿。