刷 LeetCode 的二叉树专题时617 这道合并二叉树题几乎是我每次都要推荐给别人先做的一道。原因很简单它把“递归”和“迭代”这两种最基础的解题范式压缩在一道看起来特别简单的题里。如果你能把这题吃透再去碰二叉树路径、公共祖先、树的序列化那类难题会发现底层很多思路是相通的。很多人刷这道题时会陷入一个误区看一遍递归解法觉得“好简单啊”然后直接下一题。但真到面试或写业务代码时遇到需要同时遍历两棵树的场景还是会卡壳。这篇我把自己当年啃这道题时的完整思考过程、两种解法的实现细节、还有我踩过的坑全部整理出来希望能帮你省点时间。1. 题目背后到底在考你什么先看题目本身。给定两棵二叉树 root1 和 root2要求把它们合并成一棵树。合并规则是如果两个节点位置重叠就把它们的值相加作为新节点如果某个位置只有一个节点那这个节点直接保留。这个规则听起来人畜无害但它其实比表面看起来有讲究。它要求你同时遍历两棵结构不一定相同的二叉树而且在遍历过程中要处理节点缺失的情况。这对遍历模型的理解是一个不小的考验。1.1 考察的核心能力拆解第一层是递归基本功。树本身就是递归定义的每个节点的左子树和右子树仍然是树所以处理树的问题递归往往是第一直觉。这道题里你需要在递归函数中同时接收两个树节点处理四种组合情况——双空、左空右非空、左非空右空、双非空。很多人写递归只记得“双非空加值”这一种情况漏掉其他分支结果一运行就报空指针。第二层是递归转迭代的能力。能写出递归版本的人不少但要你用显式栈或队列模拟一遍很多人就开始乱套。这里考察的是对栈调用模型的理解递归不是魔法它本质上是系统帮你维护了一个调用栈。如果你能手动用栈模拟这个过程说明你对二叉树遍历的理解已经到了“底层”级别而不是靠背模板。第三层是代码质量和边界意识。比如递归版本中当root1为空时直接返回root2很多初学者不理解为什么可以这样——他们总觉得“要合并必须新建一个节点”。但实际上你返回的是整棵子树的引用它的所有后代都已经完整存在不需要再遍历合并。这个剪枝思想在递归里非常核心。1.2 为什么这道题适合作为二叉树入门必刷我个人判断一道树题值不值得刷就看它能不能帮你建立“递归思维模型”。617 这道题最妙的地方在于它的逻辑足够简单不会像“二叉树展开为链表”那种题让你纠结指针怎么改但它的结构又足够典型覆盖了同步遍历、拷贝或修改原树、返回值语义设计这几个核心议题。刷完这道题你再去看“判断两棵树是否相同”“判断一棵树是否为另一棵树的子树”这些题会发现它们其实是同一类同步遍历两棵树只是对遍历到的情况做不同的处理。可以说 617 是这类“双树同步遍历”题型的母题。2. 递归解法把树当作文档一样剪裁合并递归解法的代码量极少但每一行都有它的分量。我在实际教学时喜欢用三要素法来拆解终止条件、返回值、单层逻辑。把这三件事想清楚了代码就是水到渠成的事。2.1 终止条件和剪枝的关键理解合并操作里终止条件不好好想清楚最容易出错。两个节点相遇无非是四种情况node1和node2都为空不需要合并返回空。node1为空node2非空合并结果就是node2的整棵子树。node1非空node2为空合并结果就是node1的整棵子树。都非空才需要值相加然后继续合并它们的左右子树。很多人会把前三种情况分开写或者干脆漏掉一两个然后稀里糊涂地报错。其实这里可以做一个化简如果node1为空就返回node2如果node2为空就返回node1。两个都为空的情况已经被自然包含在“返回另一个节点”的逻辑里了——返回空节点而已。这就是剪枝一旦某棵子树在一边不存在另一边整棵直接拿过来用不需要继续递归深入。这个思想搞懂后你会发现递归终止条件不只是“防止死递归”的保险丝它本身就是合并策略的一部分。2.2 递归关系的建立和返回值设计单层逻辑很直接合并后的根节点值等于两个根节点值之和然后合并后的左子树等于递归合并两个根节点的左子树右子树同理。这里有个关键选择是新建一棵树还是直接修改其中一棵树题目默认允许在原树上修改所以常见做法是把root1作为结果树的根直接在上面累加root2的值。这样做空间效率高因为不需要额外创建每个节点。但如果在项目里你被要求“不能修改入参”就要换成新建节点的写法。返回值的设计也很重要。递归函数返回的是“合并完的子树根节点”。父节点拿到这个返回值后需要把它接在自己的left或right指针上。这种“返回值就是拼接结果”的设计能让代码非常简洁但初学者容易漏掉赋值动作导致递归白算。2.3 递归版本的完整代码和运行过程示例以 Python 为例新建返回结果树的写法def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) - Optional[TreeNode]: if not root1: return root2 if not root2: return root1 merged TreeNode(root1.val root2.val) merged.left self.mergeTrees(root1.left, root2.left) merged.right self.mergeTrees(root1.right, root2.right) return merged如果你不想改原树只是新建一棵结果树可以在都非空时创建新节点然后递归赋值左右子树但题目通常允许改原树所以上面的写法是力扣官方里最简洁的。为了看清楚递归是不是真的“跑得对”我带一个简单例子走一遍。假设root1: root2: 1 2 / \ / \ 3 4 5 6调用mergeTrees(root1, root2)都非空创建新节点值为 123。递归合并左边3 和 5 都非空创建节点值为 8它们的左右子树都为空递归返回空。所以左边结果是节点 8。递归合并右边4 和 6 都非空创建节点值为 10左右都为空返回空。右边结果是节点 10。最终树根 3左 8右 10。如果两棵树高度不一致比如root2的某棵子树为空那递归会在第一层if not root1或if not root2处直接返回这也是合并结果里直接保留原子树的原因。这个行为天然符合题目“非空节点保留”的规则。2.4 递归写法的难点和易错点递归版最大的坑在于传递参数的配对。merged.left必须对应递归合并root1.left和root2.left不能顺手写成root1.right和root2.left。我在图快的时候犯过好几次这种低级错误结果是结构完全错乱。第二个坑是修改原树的副作用。如果你在项目里用的是直接改root1的写法调用方原来持有的root1对象会被改变后续再用它做其他逻辑时会出现奇怪的结果。所以必须养成习惯在函数文档或注释里写明“当前实现对入参进行了修改”或者干脆用新建节点的方式隔离副作用。第三个坑也是最容易被忽视的递归深度。树如果退化成一个链状结构递归深度可能达到节点数量级。力扣的题不会故意用超大数据卡递归但面试时如果你能主动提到“递归版本在最坏情况下会栈溢出所以还需要一个迭代版本”会显得你专业很多。3. 迭代解法怎么不递归也能干同样的活迭代解法和递归版本在逻辑上完全等价但需要你手动维护一个栈或者队列。核心思想是两棵树的节点不是孤立存在的当你把两个节点的配对关系压入栈中就隐式地让程序知道“待会儿还要回去处理它们的孩子”。3.1 用栈模拟先序合并的完整思路用栈来模拟递归时处理顺序是“先合并当前节点再压栈孩子”。代码结构其实很接近递归版只不过把隐式的系统调用栈变成显式栈。以 Python 为例直接修改root1的版本def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) - Optional[TreeNode]: if not root1: return root2 if not root2: return root1 stack [(root1, root2)] while stack: node1, node2 stack.pop() node1.val node2.val if node1.left and node2.left: stack.append((node1.left, node2.left)) elif not node1.left: node1.left node2.left if node1.right and node2.right: stack.append((node1.right, node2.right)) elif not node1.right: node1.right node2.right return root1逐行看这个代码。初始先把两个根节点入栈。循环体内先弹出配对节点然后将node2.val累加到node1.val。接着处理左子树如果两边左孩子都存在把配对压栈继续循环如果node1左孩子不存在直接让node1.left指向node2.left整棵左子树就算合并完了不需要再把node2.left的子孙逐个入栈。右子树同理。这个“整棵子树直接挂接”的处理是迭代版效率的关键。如果写成无论是否为空都把子节点入栈那么循环里就要处理各种空节点配对代码会非常臃肿而且边界条件容易写错。3.2 用队列实现层序版本的合并逻辑用队列代替栈就变成了广度优先的层序合并。逻辑和栈版本其实一模一样只是把pop()换成popleft()数据容器从list换成collections.deque。为什么可以用队列因为合并操作对节点的遍历顺序并不敏感。无论是先合并根、左、右还是按层从上到下合并最终对每个重叠节点执行的操作都是“值相加、处理孩子”而孩子配对入队的先后顺序不影响最终树的结构。这就是这个题目“虽然有两个解法但逻辑核心是同一个”的原因。from collections import deque def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) - Optional[TreeNode]: if not root1: return root2 if not root2: return root1 queue deque([(root1, root2)]) while queue: node1, node2 queue.popleft() node1.val node2.val if node1.left and node2.left: queue.append((node1.left, node2.left)) elif not node1.left: node1.left node2.left if node1.right and node2.right: queue.append((node1.right, node2.right)) elif not node1.right: node1.right node2.right return root1注意这段代码和栈版本几乎没有差别只是pop()变成了popleft()。这就是我要强调的核心观点迭代版本不是“另一套算法”它只是把递归时系统隐式维护的调用栈显式地换成了我们自己的栈或队列。顺序变了但合并逻辑没变。3.3 迭代版本的两个关键边界条件处理迭代版本最容易出错的就是elif not node1.left这个分支。它解决的是这样一个情况node1的左孩子不存在但node2的左孩子存在。此时你要做的是把node2.left整棵子树接到node1.left上而不是继续遍历。你可能会问为什么不继续遍历node1.left和node2.left的配对呢因为node1.left是空空节点没有子节点可再合并而node2.left这棵子树又是完整的。合并空子树和一棵非空子树结果就是那棵非空子树本身所以直接挂引用即可。这跟递归版本的剪枝思想一脉相承。另一个边界条件是根节点为空的情况。迭代版本一开始就处理了if not root1和if not root2这个判断必须放在初始入栈之前。如果你跳过这个判断直接造一个空节点入栈后面所有逻辑都会崩掉。这个“提前处理边界”的习惯在真实的算法工程里也很重要——不要让主流程去适应异常数据要在入口就挡住。3.4 栈 vs 队列你该在哪种场景下选哪个栈和队列从结果上看没区别但如果你要在一道题里同时做别的操作选择就重要了。如果合并后你需要快速访问“某一层”的节点或者要做层序遍历相关的统计用队列更自然因为它是广度优先的天然按层处理。如果合并过程中你要判断路径、做回溯用栈更顺手因为深度优先遍历和栈天然契合可以在回溯时借助栈中保存的上下文。这里还有一个实操层面的体验。栈版本在处理“一边为空、直接挂子树”时比队列版本更容易调试。因为栈的深度优先特性会让树的一侧先完整合并完你可以逐步检查这条分支对不对队列则是左右交替推进输出中间结果时比较“散”。所以我在本地调试时习惯先用栈版本确认逻辑无误后再换队列版本。4. 两种解法的复杂度分析和面试答法这道题考察的另一个维度是你能不能准确说清两种解法的时间复杂度和空间复杂度。面试官问到这里时很多人的答案是“差不多”但“差不多”三个字背后其实有值得展开的细节。4.1 时间复杂度的精确含义假设 root1 有 N 个节点root2 有 M 个节点。两种解法的时间复杂度都是 O(NM) 吗严格来说更精确的是 O(min(N, M))。为什么是 min因为合并操作只会发生在两棵树都存在的节点上。当一个节点的另外一边为空时整棵子树直接挂接不再继续遍历。所以实际访问的节点数不会超过较小那棵树的节点数。我之前看到很多人写 O(NM)严格说并不准确。如果你在面试时说 O(NM)面试官未必会反驳但如果你能主动说出来“其实是 O(min(N, M))因为只要有一边为空就整棵子树挂接了”那会给面试官留下一个很不错的印象说明你真的跑过代码而不是背过复杂度结论。4.2 空间复杂度的对比和极端情况递归版本的空间复杂度是递归调用栈的深度最好情况是 O(log N)当树平衡时最坏情况是 O(N)当树退化成链表时。迭代版本的空间复杂度取决于栈或队列中同时存储的节点配对数量。最坏情况下队列层序遍历会存储某一层的所有节点如果树接近满二叉树最后一层节点数约 N/2所以最坏空间也是 O(N)。栈版本在最坏情况下同样可能存储 O(N) 个配对节点。所以严格说两个版本的空间复杂度是同一个量级的。那为什么还要学迭代版本因为显式栈让你能控制内存的分配和释放时机。在嵌入式或高并发环境里系统调用栈的深度限制往往非常严格运行时栈溢出是整个进程崩溃级别的错误而你手动维护的堆内存栈即使内存紧张至少更容易定位是“哪个 while 循环”导致的问题。如果你在面试中说“我可以用迭代版本避免递归栈溢出”面试官通常会追问“递归栈溢出具体发生在什么时候”。这时候你如果能举出“树退化为链表、递归深度等于节点数”这个例子会非常加分。4.3 面试官追问的三个高频问题第一个追问是“能不能不修改原树返回一棵全新的树”。答案是肯定的递归和迭代都要改核心区别在于修改原树时直接相加并复用节点新建树时每个重叠节点都需要创建TreeNode对象把左右子树指针递归或迭代地构建出来。第二个追问是“如果两棵树都为空函数应该返回什么”。答案也是空。注意你写的代码是否在这个场景下仍然正确——很多人在入口写了if not root1和if not root2两个判断但顺序不对比如先判断not root2会导致root1为空、root2为空时返回空这没问题但如果root1为空、root2非空时提前返回了root2而题目要新建树那就漏了深拷贝逻辑。第三个追问是“能不能边遍历边释放 node2 节点”。这涉及到你是否理解入参对象的生命周期。如果题目允许修改原树并且你确定函数返回值是唯一结果、后续不会再用到 root2那么可以把 node2 的引用挂到 node1 上最终 root2 指向的树没有额外引用会被垃圾回收。但这属于比较激进的优化实战中不建议主动去做因为你无法控制调用方是否还持有 root2 的引用。5. 常见错误和排查技巧我帮你把坑都踩了一遍这一节我想换个角度不按官方的题解思路而是站在“如果我现在 bug 了该怎么排查”的角度来写。以下是几种常见错误和对应的调试建议。5.1 空指针报错和它的典型场景最常见的报错出现在访问node1.left前忘记判断node1是否为 null。尤其是迭代版本里你从栈里弹出配对(node1, node2)如果这个配对是在上一轮循环中由stack.append((node1.left, node2.left))产生的那么只要上一轮两个节点的左孩子都非空这里的node1才不会为空。但如果你在入栈前没有检查“非空”就盲目入栈循环里就会访问空节点的属性。排查这类问题的方法很简单在循环开头加一句调试输出打印当前弹出的两个节点的值。如果打印到某个位置出现None回头看是谁在何种条件下把它压入栈的就能精准定位是哪个分支写错了。5.2 修改原树 vs 新建树的正确选择如果题目描述说“返回新合并的二叉树”而你直接在 root1 上改那很可能被判错——不是逻辑错而是你没有正确理解题目对“返回新树”的期望。用新建节点的方式写递归时单层逻辑要注意即使root1和root2其中一个是空另一个非空格点也需要复制一份新的节点而不是直接把原节点引用返回。这里我踩过一个大坑我以为“返回原节点引用没问题”于是直接返回非空那个节点。结果测试用例里合并后我去修改返回的新树原树也跟着变了。排查了很久才意识到这个 bug 不是合并逻辑错而是“出参和入参相互引用”导致的副作用。从那以后我在写“新建树”版本时一定会问自己返回结果里的节点和入参里的节点到底是同一个对象还是不同对象这个问题的答案直接决定了我的实现方式。5.3 递归超时的几种可能性递归版超时通常不是循环卡死而是你漏掉了“剪枝”分支。比如两个节点其中一个为空时你没有直接返回而是继续往下递归就可能导致大量的重复计算。更隐蔽的情况是你已经写了if not root1: return root2但是把它放在了递归函数的中间位置或者在某个 if 块里先做了root1.val root2.val再判断空就出现“已经访问过空节点属性”的报错。排查超时问题建议在递归函数开头打印入参节点的值和地址并把空节点打印成None。这样你能直观看到每次递归进去了哪些分支很快就能发现“明明应该剪枝的地方还在深入”。5.4 常见错误速查表我整理了一张表刷题时或者写代码时可以直接对号入座错误现象可能原因排查建议AttributeError: NoneType object has no attribute val入栈/入队前没检查节点是否为空或空值处理分支缺失打印循环开头 node1 和 node2 是否为 None合并后的树结构错乱递归传参配对错误左配右或右配左检查递归调用里 left/right 是否一一对应结果正确但原树被改坏了使用了“修改原树”的实现但调用方依赖原树明确题目要求必要时采用新建节点实现大数据量测试超时缺失剪枝分支递归/循环处理了大量空子树检查一边为空时是否直接挂接整棵子树迭代版无限循环入栈后没有处理孩子配对或者孩子在某种条件下永远在栈中给循环加迭代次数上限打印每次弹出的节点对5.5 面试或写代码时的调试技巧调试递归函数时我最常用的一个技巧是“递归深度缩进打印”。给递归函数加一个depth参数然后在入口处打印 * depth fmerge({root1.val if root1 else None}, {root2.val if root2 else None})。这样你看到的就是一棵“递归调用树”哪里深了、哪里剪枝了一眼就能看出来。这个小技巧对理解任何复杂的递归题都有帮助不只是这道题。如果你用 IDE 的断点调试建议在“树节点为空”的返回分支上也打上断点这样你能直观看到剪枝发生的时机。很多时候我们以为问题出在返回值上实际上问题出在某个分支根本没有进入。6. 从这道题延伸出去一鱼多吃刷题最忌讳的是“背答案”。这道题做完后如果你只是记下了“返回 root2 的那个剪枝”那很多变式题你还是会卡壳。我的建议是把这道题当作一个原型主动去思考它的各种变形。6.1 变式合并两棵 N 叉树如果把二叉树换成 N 叉树合并逻辑的核心就变了。N 叉树每个节点有一个 children 列表合并时需要遍历两个列表对应位置的子节点两两合并。问题是列表长度不一定相同这就变成了“两个列表中较长的一方需要保留所有多出来的子节点”的问题。实际上这是在合并两个树的每层节点时对两个列表做了一次“长度对齐”的操作。这个变式题提醒我一个教训不要光记住二叉树的“左-右”配对要理解“配对”的本质是“对应位置”。二叉树结构中每个节点的 children 数量是固定的 0-2所以配对天然是显式的左/右N 叉树里配对需要你用一个for循环去按索引对齐。6.2 变式合并两棵树并统计合并后的信息面试官有时候不会直接考“合并”而是把合并包装进一个统计任务里。比如“合并两棵二叉树返回合并后的树的最大深度”。这题的思路就变成了先合并再求深度。或者你可以在递归过程中直接返回值——合并后的子树根节点的高度由左右子树的高度决定这样你就不用单独再做一次遍历了。这种“边合并边计算”的写法本质上是对原递归函数的返回值语义做了一个扩展。原来返回的是合并后的子树根节点现在直接返回一个(根节点, 高度)的二元组。如果你对原始问题理解得足够深这个变式很容易就能写出来。它考察的正是“递归返回值能不能按需要重构”的能力。6.3 变式不修改原树的合并要求保持原树不变这个变式在业务代码里非常常见。你的入参可能是共享对象被多个服务同时引用绝对不能改动。这种情况下递归版本里每次都要新建节点def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) - Optional[TreeNode]: if not root1 and not root2: return None if root1 and not root2: return TreeNode(root1.val, self.mergeTrees(root1.left, None), self.mergeTrees(root1.right, None)) if root2 and not root1: return TreeNode(root2.val, self.mergeTrees(None, root2.left), self.mergeTrees(None, root2.right)) return TreeNode(root1.val root2.val, self.mergeTrees(root1.left, root2.left), self.mergeTrees(root1.right, root2.right))注意这里单侧为空时也要继续递归因为你需要把非空那侧的所有后代节点都完整复制一份。如果你只在入口判断if not root1: return root2返回的仍然是原对象就没有做到“新建”。这是我当时最容易忽略的细节。你写完这个版本后可以用“修改返回树的节点值检查原树是否变化”的方式来自测。如果能保证原树不变那这个版本才算写对。这些变式题不用全刷但建议在脑子里过一遍思路面试时一旦被追问你能条件反射般地给出方案。最后再分享一个我在实际编码中的体会这道题的递归版本和迭代版本本质上是一枚硬币的两面。你不需要硬背两种模板只需要把“同步遍历两棵树处理重叠节点剪枝空分支”这个核心模型吃透其他树类的双指针题目——判断子树、判断相同树、合并有序链表——都会变得顺手很多。我自己刷题这么多年遇到树的问题第一反应永远是“递归能不能写”因为递归版本在逻辑清晰度上永远是第一位的只有在需要严格控制栈深或面试官明确要求时我才会切换成迭代实现。希望你也能找到属于自己的切换节奏而不是被某一个模板框住。