直接看题。LeetCode 100 Same Tree判断两棵二叉树是否相同。这题在 LeetCode 上难度标的是 Easy但如果你去翻一下热门100题、周赛题解和各种刷题指南会发现它几乎出现在每一份“二叉树入门必刷清单”里。我在刷题前几周其实有点看不上这种简单题觉得不就是递归比一下节点吗真正静下心把递归、迭代、以及它的几个变体题全部吃透之后我才意识到自己当初错得离谱——这道题根本不是“判断两棵树是否相等”这么简单它本质上是整类“双树同步遍历”问题的原型后面遇到对称二叉树、子树判断、翻转等价树全都是 Same Tree 这颗种子长出来的。这篇文章我打算按自己的刷题复盘逻辑来写。先把这题的考点拆透然后分别走一遍递归解法和迭代解法重点讲迭代法里非常容易被忽略的细节再顺藤摸瓜把相关的变体题串起来最后给出一组我每次重刷都会跑的测试用例。无论你是刚开始刷 LeetCode 的新手还是准备面试想快速过一遍二叉树重点题的老手这篇都能给你一点不一样的东西。1. 先弄明白这道题究竟在考察什么很多题解上来就贴代码然后加一句“递归遍历即可”。代码确实没错但如果你只是背下了这段递归遇到稍微变形的题目还是会懵。所以我习惯先弄清楚题目到底想考我什么1.1 题目的真实诉求结构一致性 值一致性题目描述很直白给定两棵二叉树的根节点 p 和 q判断它们是否相同。什么叫“相同”官方定义是结构相同并且节点具有相同的值。拆开看就是两个条件结构一致两棵树在每个对应位置上的“有没有节点”必须完全相同。p 的某个子树为空q 的对应子树也必须为空。值一致对应位置上的节点值必须相等。“结构一致”这一点很容易被新手忽略。我见过不少人写出来的递归只比较了 val没有认真处理空节点结果遇到[1,2]和[1,null,2]这种用例就挂了。这两棵树根节点都是 1但一个右子树有节点、另一个左子树有节点结构完全不同显然不相等。还有一个很容易绕进去的点这里的“相等”到底按什么语义LeetCode 的 TreeNode 是引用类型但我们判断的是“两棵树的值和结构”不是判断两个引用是否指向同一块内存。也就是说即使 p 和 q 是两个完全独立的对象只要它们构造出来的树形态和值一样就返回 true。1.2 核心本质同步推进的两个指针这道题最底层的模型我觉得可以这样理解你手里有两个指针一个指向 p 的某个节点另一个指向 q 的对应节点。每一步两个指针同时移动移动到两棵树里“位置对应”的节点上。如果某一步发现两个指针一个指向空、一个指向非空或者两个都非空但值不同直接判 false。如果同步走完了整棵树都没有出现不一致说明两棵树相同。这个“同步推进”的思想就是 Same Tree 想考察的第一性原理。单棵树的遍历你只需要维护一个指针而双树比较需要时刻维护一对指针的同步关系。后续无论递归还是迭代本质上都是对这个模型的实现。复杂度也先说清楚假设两棵树的节点数分别是 n 和 m最坏情况下你需要把较少的那棵树完整走完才知道结果所以时间复杂度是O(min(n, m))。递归版本的空间复杂度取决于递归栈深度正常平衡树是O(log n)最坏退化成链状树时是O(n)。迭代版本用显式栈空间复杂度同样最坏是O(n)。2. 递归解法三行代码背后的同步推进思想递归版是这道题最自然的解法几乎所有题解都会先给这个版本。代码写出来很短但每一行都有讲究。我先给 Python 版本# Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # self.val val # self.left left # self.right right class Solution: def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) - bool: if not p and not q: return True if not p or not q or p.val ! q.val: return False return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)JavaScript 版本写法也差不多var isSameTree function(p, q) { if (!p !q) return true; if (!p || !q || p.val ! q.val) return false; return isSameTree(p.left, q.left) isSameTree(p.right, q.right); };就是这三行核心判断加上一行递归调用。但你要是问面试官“为什么这样写是对的”能答清楚的人其实不多。2.1 终止条件的顺序为什么“先判空”不能省看递归代码第一件事永远是处理空节点。有人可能觉得这是防御性写法其实不是。树的结构天然是递归的而空节点就是递归的“底部”。没有空节点判断递归就没有出口。更关键的是判断顺序。很多人会写成这样if (p.val ! q.val) return false; if (!p || !q) return false;这样写会直接空指针报错——如果 p 或 q 是 null你根本访问不到.val。所以必须先保证你在访问值之前已经确认了两个节点都非空。这里有个小技巧递归里的第二个条件!p || !q || p.val ! q.val三个判断用||连在一起靠的是 JavaScript 的短路求值。从左到右执行时只要!p为真后面的!q和p.val根本不会执行也就不会触发空指针。Python 的or同理。这个写法比写成三个嵌套 if 更紧凑而且逻辑上是完备的第一个 if两个都为 null说明当前位置结构一致且没有值需要比较返回 true。第二个 if恰好覆盖了所有需要返回 false 的情况——一个为空另一个不为空、两个都不为空但值不同。走到第三个 return说明两个节点都非空且值相等于是继续递归比较左子树和右子树。2.2 从递归到“分治”视角为什么这个递归是正确的因为它把原问题拆成了三个子问题当前两个根节点值是否相等左子树是否相同右子树是否相同。三个子问题全部成立原问题才成立。这就是标准的“分治”思路自顶向下把问题分解到最小单元空节点自底向上逐层返回结果。注意递归调用里用的是andPython或JavaScript。这个逻辑运算符本身就带了短路性质如果左子树已经不相同了右子树根本不会执行递归。这是一个很自然的性能优化虽然对复杂度的大 O 量级没有影响但确实能避免不少无效计算。我在刷题初期对递归总有一种“玄学感”——明明每一步都知道在干什么但整体总是觉得悬空。直到我自己在纸上画了一棵三层高的树手动模拟了递归调用的完整路径之后才算真正建立了“递归信任”你不需要关心整个递归过程的所有细节只要保证当前层的逻辑正确并且相信子问题会返回正确结果。Same Tree 这道题的递归恰恰是建立这种信任感最好的练手题目之一。2.3 递归解法的边界条件测试写递归最容易翻车的地方就是边界条件。以我自己的经验下面这些 case 是每次写完必须立刻在脑子里过一遍的两棵树都为空返回 true。这个用例测试的是第一个 if 的分支很多人在这个 case 上写错过——比如只判断了一个为空就返回 false。两棵树一棵为空另一棵不为空返回 false。这个 case 测试的是第二个 if 中!p || !q的逻辑。注意这个分支的返回值是 false因为一个节点存在、另一个不存在结构已经不一致了。根节点值相同但左右子树结构不同返回 false。比如[1,2,3]和[1,2,null,3]左子树都是 2右子树一个是 3 一个是 null递归到右子树比较时触发!q为 true。这些用例看起来简单但真正在 LeetCode 上提交的时候第一版代码经常就是在这些边界上挂掉。3. 迭代解法用显式栈模拟递归时最容易踩的三个坑递归版虽然简洁但有一个天然的短板当树很深的时候递归调用栈可能爆掉。工程上处理几百万节点的树时递归往往不现实而且面试中面试官经常会在你给出递归解之后追问“如果递归深度太大怎么办能不能改成迭代”所以迭代版不是可选项是必选项。Same Tree 的迭代版核心思路也很清晰用一个栈或队列保存“等待比较的节点对”每次弹出一对比较然后把它们对应的子节点对继续压入栈中。下面是 Python 的栈实现class Solution: def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) - bool: stack [(p, q)] while stack: node1, node2 stack.pop() if not node1 and not node2: continue if not node1 or not node2 or node1.val ! node2.val: return False stack.append((node1.left, node2.left)) stack.append((node1.right, node2.right)) return TrueJavaScript 版var isSameTree function(p, q) { const stack [[p, q]]; while (stack.length) { const [node1, node2] stack.pop(); if (!node1 !node2) continue; if (!node1 || !node2 || node1.val ! node2.val) return false; stack.push([node1.left, node2.left]); stack.push([node1.right, node2.right]); } return true; };这段代码看起来也不复杂但里面藏着三个特别容易忽略的细节。我当年学迭代法的时候三个坑全踩了一遍一个一个说。3.1 坑一空节点到底要不要入栈新手写迭代版最常见的错误是只把非空的节点对压入栈。比如// 错误示范 if (node1.left node2.left) stack.push([node1.left, node2.left]);这样写看起来“优化”了空间但会直接导致结构差异被漏判。举个最简单的反例p [1, null, 2]q [1, 2, null]根节点都是 1值相等。p 的右子树有节点 2q 的左子树有节点 2右子树为空。如果只在两边都非空时才入栈p 的右子树和 q 的右子树虽然某个节点为空但因为不满足“都非空”的条件就不会被比较最终可能错误地返回 true。正确做法是空节点也要作为“占位符”成对压入栈中。上面代码里stack.append((node1.left, node2.left))这一行无论 node1.left 和 node2.left 是否为空都会把这一对压进去。这样到下一次弹出时如果发现!node1 !node2说明两边都为空结构一致继续循环如果发现一个为空另一个不为空触发!node1 || !node2分支直接返回 false。所以这里根本没有“优化空节点不入栈”的空间。空节点入栈不是浪费它是保证结构比较正确性的必要手段。3.2 坑二入栈顺序与比较顺序的一致性第二个坑和栈的 LIFO后进先出特性有关。看一下上面代码里的入栈顺序stack.append((node1.left, node2.left)) stack.append((node1.right, node2.right))因为栈是后进先出所以下一次弹出时先处理的会是右子树对然后才是左子树对。也就是说这段代码实际上采用的是“根 - 右 - 左”的遍历顺序。这在 Same Tree 的判断里完全没问题因为我们要比较的是整棵树的结构和值遍历顺序本身不影响最终结果。但你需要保证的是每次弹出的一对节点一定来自两个树中结构位置相同的节点。只要压栈时总是把“左子树对”和“左子树对”放在一起、“右子树对”和“右子树对”放在一起这个对应关系就不会被破坏。如果你把顺序写成stack.append((node1.left, node2.left)) stack.append((node1.right, node2.right))或者反过来stack.append((node1.right, node2.right)) stack.append((node1.left, node2.left))都没有问题因为比较顺序变了但配对关系不变。可如果你粗心写成(node1.left, node2.right)这种交叉配对那就彻底错了。这种错误通常不会立刻暴露而是会在某个特殊用例上翻车排查起来非常痛苦。顺带一提把栈换成队列就是 BFS 的层序比较版本。入队顺序是“先左后右”出队顺序变成了“先入先出”。逻辑上完全一致只是遍历顺序变成了层序。LeetCode 讨论区里有些题解更喜欢用队列因为 BFS 对某些人来说更直观。我个人觉得栈和队列在这道题上没有本质区别选哪个纯粹看习惯。不过如果面试官追问“DFS 和 BFS 在这题里有什么不同”你要能答出来一个是深度优先、一个是广度优先但判断两棵树相同的充要条件与遍历顺序无关两者的正确性是等价的。3.3 坑三循环终止条件的写法第三个坑是关于 while 循环什么时候结束。标准写法是while stack:也就是栈空了才退出。这个条件意味着所有节点对都已经比较完毕且没有出现过不一致。有一种看起来等价的写法是while stack and (node1 or node2):但这种写法加上了“当前节点对必须至少有一个非空”的条件。实际上这个额外的条件是不需要的因为如果弹出的两个节点都是 null在循环体内continue后栈若空了循环本来就会正常结束。你多加一个条件反而会破坏逻辑——万一栈里还剩其他待比较的节点对你却提前退出了结果就错了。还有一个小细节初始时如果 p 和 q 都为空上面的代码是怎么处理的栈初始化为[(p, q)]也就是[(None, None)]。进入循环后弹出这一对满足not node1 and not node2执行continue。此时栈为空循环退出返回 true。所以不需要在代码开头单独写if not p and not q: return True这种特殊分支循环本身已经覆盖了这个 case。3.4 递归与迭代的本质一致性把递归解法和迭代解法放在一起看你会发现它们本质上是在做同一件事同步遍历两棵树逐对比较节点。递归把“待比较的节点对”放在系统调用栈里迭代把它放在显式栈里。区别只是控制流的管理方式不同。理解了这一点你就不会再问“这道题到底用递归还是迭代”这种问题了。选择依据很清晰如果树深度可控递归代码更简洁、可读性更好如果树的深度可能非常大或者面试官明确要求你避免系统栈溢出的风险就用迭代。两者都要会写这才是这道题作为“必刷题”的真正意义。4. 从 Same Tree 延伸出去的同类题一题带出一串Same Tree 的价值不仅在它本身更在于它是很多进阶题的“种子题”。我把这些变体题放在一起刷发现它们的核心模型都是“双树同步遍历”只是在比较规则上做了各种变化。这里挑几道最典型的展开说说。4.1 LeetCode 101 对称二叉树从“左对左”变成“左对右”对称二叉树问的是判断一棵二叉树是否关于根节点轴对称。等价于把根节点的左子树和右子树看成两棵树判断它们是否是“镜像相等”的。什么叫镜像相等就是 p 的左子树对应 q 的右子树p 的右子树对应 q 的左子树。对比 Same Tree 的代码唯一的区别就是递归那一行的参数顺序# Same Tree return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right) # 对称二叉树 return self.isSameTree(p.left, q.right) and self.isSameTree(p.right, q.left)看出门道了吗Same Tree 是结构位置一一对应对称二叉树是“交叉对应”。把 101 题做一遍你对 Same Tree 的理解会立刻加深一层。4.2 LeetCode 572 另一棵树的子树双重递归的经典场景这道题问的是给定两棵二叉树 root 和 subRoot判断 subRoot 是否是 root 的子树。也就是说root 中是否存在某个节点以它为根节点的子树和 subRoot 完全相同。这题的解法本质上就是一个“遍历 比较”的组合遍历 root 的每一个节点对每个节点调用 Same Tree 的逻辑判断它和 subRoot 是否相同。代码框架大概是def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) - bool: if not root: return False return self.isSameTree(root, subRoot) or self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)这里有个很经典的坑很多人会把isSameTree直接嵌进isSubtree里导致一个函数里既有“遍历”又有“比较”逻辑混在一起边界条件特别容易出错。正确的思路是把两个问题拆开——一个负责遍历一个负责比较。这也是为什么我强调 Same Tree 一定要先吃透因为它是 572 题的比较组件。另外572 题还有一个容易出错的点根节点为空的情况。这种边界如果不处理好很容易陷入死循环或者空指针。4.3 LeetCode 951 翻转等价树比较规则再变种接下来是翻转等价树两棵树如果可以通过若干次“交换任意节点的左右子树”变成相同就认为翻转等价。这题的比较规则比对称二叉树更复杂一点两个节点的左右子树可以相等也可以交叉相等。def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) - bool: if not root1 and not root2: return True if not root1 or not root2 or root1.val ! root2.val: return False return (self.flipEquiv(root1.left, root2.left) and self.flipEquiv(root1.right, root2.right)) or \ (self.flipEquiv(root1.left, root2.right) and self.flipEquiv(root1.right, root2.left))这个递归的返回条件里第一个括号对应“不翻转”的情况第二个括号对应“翻转”的情况。本质还是 Same Tree 的框架只不过把比较逻辑从一个确定性的映射变成了两个可选项。如果 Same Tree 的同步遍历思想没吃透这题很容易绕晕。4.4 LeetCode 872 叶子相似树把树“序列化”后再比较叶子相似树问的是两棵树的叶子序列是否相同。解法思路也很直接分别遍历两棵树收集所有叶子节点得到两个序列再比较序列是否相同。这个题表面上不像 Same Tree但你会发现它底层的思想是一样的——都要求你“同时处理两棵树的对应位置”。只不过对应位置从“节点”变成了“叶子序列中的元素”。我在面试中被问过类似的问题面试官会说“你能不能不用额外空间同步遍历两棵树来比较叶子序列”这就需要你同时维护两个遍历状态每次各取一个叶子出来对比。这比先收集序列再比较要难因为两棵树的结构可能不同走到下一个叶子的步数不一样。这也算 Same Tree 思想的进阶应用了。4.5 面试官常问的变体提问结合上述题目我再整理几个面试里常见的追问如果只判断结构相同、不判断节点值怎么做把递归判断p.val ! q.val这一行去掉即可。如果只判断值相同、不判断结构怎么做那就不叫“树”了需要把所有节点值按某种遍历序收集出来再比较但这种做法丢掉了位置信息所以不能覆盖结构差异。如果节点值可能重复能用哈希来加速判断吗对于完全比较两棵树哈希没有意义因为你要比的是每个对应位置的值而不是节点值的集合两棵树的值集合相同不代表结构相同。如果两棵树特别大内存有限怎么办这是迭代法出场的时候了但即便迭代法最坏情况空间复杂度仍是 O(n)。想做到严格 O(1) 额外空间就需要用到 Morris 遍历的思路来模拟栈。这个作为进阶拓展了解即可。这一串题刷下来你会明显感觉到同一颗种子长出的枝叶可以千变万化但根茎始终是“同步遍历两个树结构”。5. 刷题复盘我重新做这道题时的几个测试用例最后这部分我想分享一些关于测试和复盘的心得。很多刷题攻略都会强调“多刷几遍”但没有人说清楚每一遍应该怎么看。以 Same Tree 为例我每过一段时间就重刷一次每次都会用下面这组测试用例来验证自己的代码。它们覆盖了这道题所有容易出错的角落。5.1 一组覆盖全部边界的测试用例我先给出一棵基础树作为参照1 / \ 2 3用 LeetCode 的数组表示法就是[1,2,3]。针对这个参照我至少会跑这些用例用例pq期望结果验证点1[]null[]nulltrue两棵空树2[]null[1]false一棵空一棵非空3[1][2]false根节点值不同4[1,2][1,null,2]false结构不同但值可能部分相同5[1,2][1,2]true普通正常情况6[1,2,3][1,2,3]true两棵完全相同的三节点树7[1,2,3][1,3,2]false左右子树互换结构值都不一致第七个用例很容易被忽略。[1,2,3]和[1,3,2]的根节点都是 1节点集合也都是 {1,2,3}但树的结构不同所以不是相同的树。5.2 我第一次写这道题时犯的错误坦白说我第一次独立写 Same Tree 的时候递归版提交了两次才通过。第一次挂掉的用例就是[1,2]和[1,null,2]。我当时的代码大概是这样的if p is None or q is None: return False if p.val ! q.val: return False return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)看起来没什么问题其实漏了“两个都为 None 时返回 True”这个分支。当递归比较到 p 的左子树是 None、q 的左子树也是 None 时我的代码会走进p is None or q is None直接返回 False。当然这是错的因为两棵树的左子树都为空这一个位置的结构是一致的应该继续往后比较。后来我调整了判断顺序把“都为空返回 true”放在最前面这才算真正理解了终止条件的完整逻辑。这也是为什么我在第 2 节那么强调终止条件顺序的原因——这是我自己实打实踩过的坑不是从教科书上抄来的理论。5.3 重刷时我推荐的做法如果你准备重刷这道题我建议不要直接看答案先把书合上自己写。下面是我的具体流程先写递归版要求自己在 5 分钟内写完并且保证一次通过所有边界用例。写的时候心里默念三个问题的答案两个都为空怎么办一个为空一个不为空怎么办两个非空但值不同怎么办然后立刻写迭代版要求自己用栈实现 DFS再改成队列实现 BFS。如果两个版本都能在三五分钟内无错写出来说明这道题你真的掌握了。最后做一件额外的事把递归版里面的改成||或者在迭代版里故意调换一下压栈顺序然后自己跑测试用例观察结果怎么变。这种“故意写错”的练习方式比单纯刷十遍题更能加深理解因为你是在主动探索代码的行为边界。LeetCode 周赛里经常出现一些二叉树相关的题目很多时候基础题的变化版本会拼接到中等题里。把 Same Tree 当成基本功练扎实比赛的时候至少能少花五分钟在这类比较逻辑上。落笔到这里我觉得关于 Same Tree 能讲的干货基本都覆盖了。最后分享一个小经验三道树的入门题Same Tree、Maximum Depth of Binary Tree、Invert Binary Tree我每次面试前都会花十分钟重新过一遍不是为了背诵而是为了把“递归 树”的手感保持在最佳状态。就像运动员赛前热身一样这几道题就是属于刷题人的热身动作。等你把递归版和迭代版都写到肌肉记忆的程度再去碰 101、572、951 那一串变体题你会发现自己已经站在了一个完全不同的起点上。