对称二叉树判断：递归与迭代解法实战解析

1. 题目到底在问什么从一棵树谈对称的本质刷过LeetCode热题100的朋友应该都有这种感觉二叉树这块的题很多是“看着简单写着崩溃”。对称二叉树就是最典型的一道题号101名字叫Symmetric Tree。题目本身短得让人放松警惕——给你一棵二叉树的根节点判断它是不是对称的围绕中心看树是不是自己的镜像。很多人第一次看到这题第一反应是“把根节点左右两棵子树拿出来比较一下不就完事了”。这个直觉方向没错但实现起来有个大坑你不能只比较左右两个根节点你得逐层往下比较而且比较的方向是交错的。左子树的最左边节点要对应右子树的最右边节点左子树的右节点要对应右子树的左节点。如果只比较同一层次相同位置的节点就会把真正的镜像关系误判成“长得一样”一道简单题硬是让你做出错解来。说这道题适合谁我觉得有三类人。第一刚学完二叉树基本概念、想找一道入门题练递归的新手第二准备面试、想在最短时间内掌握递归和迭代两套写法的求职者第三被空指针异常、递归栈溢出折腾过、想系统性排查二叉树运行时错误的老手。这道题其实是一个极好的“空节点处理”训练场因为对称性的判断核心就在“怎么处理空节点”这几个字里。1.1 原题描述与对称定义原题给的例子很直白。第一棵树1 / \ 2 2 / \ / \ 3 4 4 3这棵树是对称的因为围绕根节点画一条中轴线左右两边完全镜像。第二棵树1 / \ 2 2 \ \ 3 3这棵树就不是对称的虽然左右根节点都是2但左子树的2没有左孩子、只有右孩子3右子树的2却只有右孩子3镜像过去应该是左边有右孩子、右边有左孩子现在两边都挤在右边镜像关系就崩了。这里最核心的定义要抠细一棵树对称意思是对于任意一对镜像位置上的节点它们的值相等而且镜像位置上要么同时为空、要么同时不为空。关键是“镜像位置”这四个字不是“对应位置”。左子树的左孩子镜像过去是右子树的右孩子左子树的右孩子镜像过去是右子树的左孩子。这个交错关系就是整道题的命门。1.2 为什么第一反应“左右相等”是错的我最初刷这题时先入为主地写了个层序遍历版本把每一层的节点按从左到右的顺序收集到数组里然后判断这个数组是不是回文。第一版测试用例直接过信心满满地提交结果栽了。原因在于层序遍历的数组回文只能证明“每一层从左到右的节点序列”是回文但节点的左右位置信息已经模糊了。比如一棵树某层有节点值为[3, 4, 4, 3]它回文但4在左子树的哪个分支、在右子树的哪个分支完全看不出来你无法用一维数组还原二叉树那种交错的位置关系。后来我才意识到对称性本质上是“树的几何镜像”必须按镜像对去比较。你比较的每一对节点一个来自左子树的某个方向另一个必须来自右子树的相反方向。所以这道题真正的考点不是遍历而是递归结构的设计或者说是“你怎么把两棵子树的递归比较建模出来”。想清楚这一点后面的写法就顺了。2. 核心解法一递归自顶向下比较镜像节点递归是二叉树题的默认武器对称二叉树当然也不例外。递归的思路一句话就能说清从根节点出发把整棵树的对称性拆解成左右两颗子树的镜像比较而判断两棵子树是否互为镜像只需要递归地比较四组节点左子树的左孩子 vs 右子树的右孩子以及左子树的右孩子 vs 右子树的左孩子。这个方法我愿称之为“镜像递归”模板固定、代码极短、不容易写错是面试时最稳的解法。2.1 递归函数的参数设计很多新手写递归死在第一步不知道递归函数要几个参数。这里有一个很关键的思维转换——不要写“判断一棵树是否对称”的函数要写“判断两棵树是否互为镜像”的函数。也就是说递归函数的入参是两个节点分别是左树上要比较的节点和右树上要比较的节点。代码是这样设计的Python版本直接用LeetCode的TreeNode结构class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right class Solution: def isSymmetric(self, root: TreeNode) - bool: # 空树自然是对称的 if not root: return True # 主任务比较根节点的左右两棵子树是否互为镜像 return self.isMirror(root.left, root.right) def isMirror(self, left: TreeNode, right: TreeNode) - bool: # 两棵子树互为镜像的条件 # 1. 当前两个节点的值相等 # 2. 左树的左孩子 与 右树的右孩子 互为镜像 # 3. 左树的右孩子 与 右树的左孩子 互为镜像 if not left and not right: return True if not left or not right: return False return (left.val right.val) and self.isMirror(left.left, right.right) and self.isMirror(left.right, right.left)看到没有这个函数没有去“遍历”整棵树而是定义了一个递归关系。isMirror(left.left, right.right) 这一步就是镜像的核心左树的左对的是右树的右。isMirror(left.right, right.left) 是镜向的另一个方向左树的右对的是右树的左。两个方向都要成立当前节点才能算镜像。2.2 终止条件与返回值怎么写递归最容易翻车的就是终止条件。这道题反而很清晰只有三种情况两个节点都为空返回True一个为空一个非空返回False两个都不为空就比较值值相等且子树镜像才返回True。这里要特别强调一个细节两个节点都为空时返回的是True不是False。为什么因为子树到尽头了说明一路比较下来没有出现不一致当前比较分支是对称的应该把判断结果“向上传递”由别的分支决定整棵树是否对称。很多同学写的时候会把“两个都为空”写成返回False然后整个函数逻辑全乱跑出来的结果是“一棵只有根节点的树不对称”。这就是把终止条件的语义搞反了。空对空是匹配的不是失败的。只有空对非空才是匹配失败。这段逻辑还有一种更简洁的写法一气呵成很多题解里能看到def isMirror(self, left: TreeNode, right: TreeNode) - bool: if not left and not right: return True if not left or not right: return False return left.val right.val and self.isMirror(left.left, right.right) and self.isMirror(left.right, right.left)注意这里的短路求值如果当前两个节点值都不相等那后面的递归根本不会执行直接返回False节省了大量无效比较这也是递归写法的一个隐性优势。2.3 时间空间复杂度时间复杂度上每个节点只会被访问一次所以是O(n)n是树的节点数。空间复杂度是递归栈的深度最坏情况是一棵严重偏向的单支树递归深度达到O(n)但那种树在这个场景下很快就会因为镜像不匹配返回实际栈深度取决于比较路径的长度。平均情况下是O(log n)因为平衡树的递归深度只有树高。这里有一个经验可以分享这道题的空间复杂度不会成为面试焦点但如果你被问到“能不能用迭代把递归栈变成显式栈”那就是在引导你往下一个解法走紧接着把迭代方案亮出来面试节奏就牢牢抓在手里了。3. 核心解法二迭代用栈和队列模拟递归递归虽然好写但有时候面试官会追问一句“如果树的深度特别大递归栈扛不住怎么办”或者干脆要求“换一种非递归实现”。这时候就需要迭代写法顶上。迭代的本质是用显式的栈或者队列自己模拟递归过程中的节点配对比较。迭代写法的核心也是把两棵子树上的节点两两配对压入容器中再成对弹出比较。换汤不换药关键在于配对顺序。3.1 为什么需要迭代先说个实际场景。LeetCode很多题目的测试用例不会刻意构造一万层深的树但生产环境的业务数据可不讲道理曾经有朋友做目录树解析时递归处理一个深度超过2000的嵌套结构直接把程序栈打爆了。递归虽好深了就有栈溢出的风险。如果你写的是需要部署到服务端的代码能用迭代的地方尽量迭代这是工程上的素养。对称二叉树用迭代还有个好处一旦在比较过程中发现不对称的节点对可以立刻返回False不需要把剩余节点全处理完某些场景下能提前结束省时间。3.2 用栈实现镜像比较栈版本的思路是初始把 root.left 和 root.right 这一对节点压入栈每次循环弹出一对节点进行比较根据比较结果决定继续压入下一批节点对还是直接返回False。class Solution: def isSymmetric(self, root: TreeNode) - bool: if not root: return True stack [(root.left, root.right)] while stack: left, right stack.pop() if not left and not right: continue if not left or not right: return False if left.val ! right.val: return False # 注意压入顺序两两成对 # 左树的左 vs 右树的右 stack.append((left.left, right.right)) # 左树的右 vs 右树的左 stack.append((left.right, right.left)) return True这里有个细节要格外小心压入栈的对必须是“镜像对”不能随手压成(left.left, right.left)。一旦配对错了比较的就是同一侧的位置而不是镜像位置整道题就做成了“比较两棵子树是否相同”而不是“是否互为镜像”。这个错误我在初学时犯过调试了半天才意识到是特别容易踩的坑。另外压入顺序本身对结果没有影响。你先把(left.right, right.left)压进去再压(left.left, right.right)也完全没问题因为栈只是临时存放待比较的对先后顺序不影响最终判断。但建议保持固定顺序代码可读性更好也方便别人review理解你的思路。3.3 用队列实现BFS比较队列版本和栈版本长得几乎一样区别只是把 append 和 pop 改成 append 和 pop(0)或者用 collections.deque 提升性能。因为队列是先进先出处理顺序就变成了逐层推进有点BFS的意思。我通常更推荐用collections.deque因为列表的pop(0)是O(n)操作迭代多次之后性能有损耗。from collections import deque class Solution: def isSymmetric(self, root: TreeNode) - bool: if not root: return True queue deque([(root.left, root.right)]) while queue: left, right queue.popleft() if not left and not right: continue if not left or not right: return False if left.val ! right.val: return False queue.append((left.left, right.right)) queue.append((left.right, right.left)) return True队列版本理解起来比栈版本更直观每一轮从队列头部取出一对待比较节点然后把它们各自的镜像孩子塞到队列尾部一层一层地往外扩散。如果一路比较都匹配最终队列会清空返回True。3.4 两种迭代代码对比写到这里你可能会问栈和队列到底用哪个我的答案是都可以看使用场景。这里整理一个对比表对比维度栈实现队列实现数据结构显式栈模拟递归队列模拟逐层比较遍历顺序深度优先后进入的先比较广度优先按层比较性能无额外差异无额外差异推荐场景面试手写逻辑紧凑习惯BFS或想逐层验证思路代码量基本相同基本相同实际刷题时手写栈版本更常见因为它和你脑子里“递归改迭代”的思路最接近面试官也容易跟上你的逻辑链。队列版本更适合作为补充展示表现出你了解不止一种实现路径。两种都写熟了这道题就算吃透了。4. 常见运行错误与排查实录我一直觉得判断一个人二叉树功底扎不扎实不是看他能不能写出答案而是看他碰到运行时错误时怎么排查。热词里那句“写二叉树程序时为什么总是报运行时错误”真的戳中太多人的痛点了。对称二叉树这道题正好是各种运行错误的集大成者。下面把我在刷题和帮人debug时遇到的高频问题一条条拆开讲。4.1 空指针访问是最常见的翻车现场空指针报错几乎是二叉树新手的第一道坎。最常见的写法是if left.val ! right.val: return False这句话写在“两个节点都不为空”的检查之前那如果left或right是None访问.val直接炸LeetCode会给你报一个AttributeError看到这种错误基本可以断定某个节点对里出现了None而你提前解引用了。正确的顺序一定是先判空、再比价。把空判断放在值比较之前这也是我反复强调空值逻辑优先的原因。很多人图省事觉得“这棵树肯定不是空树”结果测试用例里全是极端情况一提交就现原形。还有一种隐蔽的空指针场景你在递归函数里没有判断当前节点是否存在就直接访问当前节点的left和right。比如写成 return self.isMirror(left.left, right.right)如果left本身是None访问left.left直接崩溃。所有的递归调用都要建立在节点非空的基础上或者让递归函数的终止条件先去处理空节点。4.2 递归栈溢出与迭代兜底递归写法有个天然风险树高很大时系统调用栈会被打爆。LeetCode的默认测试数据基本不会出现这种极端情况但面试官问起“如果这棵树的深度是10000怎么办”你要能接话。答案就是切换到迭代写法用显式栈或者队列。硬件栈空间是固定的你用一个Python列表或者deque只要内存够几千甚至上万层都能扛。这里有个小技巧如果遇到递归栈溢出的报错RecursionError而你又不想重写成迭代可以先检查是不是递归终止条件写错了。有时候不是树太深而是你的递归没有收敛比如某个递归调用传入了错误的参数导致永远走不到空节点分支那栈溢出就是必然的。4.3 递归结果被逻辑短路吞掉还有一种很难发现的错误逻辑上没报错但结果不对。比如新手容易把返回逻辑写成if left.val right.val: if self.isMirror(left.left, right.right): return True return False return False这种写法看着也能过简单用例但逻辑有问题。它的意思是“只要左子树的左和右子树的右镜像成功就返回True”完全忽略了还有一组镜像对要比较。正确写法是同时判断两组镜像关系用and连接两个递归结果return left.val right.val and self.isMirror(left.left, right.right) and self.isMirror(left.right, right.left)这一点值得多说一句二叉树的对称性验证要求“所有”镜像对都成立漏掉任何一组都会误判。用and连接一旦某组镜像不成立整个结果就是False这才是符合题意的合并逻辑。4.4 调试技巧画图比对不如打印配对刷二叉树题时最忌讳的就是盯着代码空想。我调试对称二叉树时的习惯是打印每一对待比较节点的值。可以在迭代版本里临时加一行打印while stack: left, right stack.pop() print(left.val if left else None, vs, right.val if right else None)这一行打出来整个比较过程一目了然。比如你会看到(3, 3)比对成功紧跟着(4, 4)比对成功再往下一层全部出现(None, None)说明这棵树确实对称。如果哪一步打印出来是(3, None)或者(None, 4)那棵树的不对称点就在那里你连“哪一层出错”都看得清清楚楚。4.5 常见问题速查表现象可能原因解决办法AttributeError: NoneType object has no attribute val判空逻辑写在值比较之后先判空再比较值RecursionError: maximum recursion depth exceeded递归终止条件缺失或结构失衡检查末尾递归调用是否正确改用迭代写法结果答案错误但单测用例能过镜像配对方向写错检查压栈/递归参数左.left要对应右.right结果答案错误说的“不对称”判成了对称漏比较一组镜像对用and同时连接两路递归结果程序超时pop(0)频繁使用或递归重复访问用deque替代list检查是否重复比较同一条路径5. 从对称二叉树延伸镜像、同构与遍历的误区刷一道题如果只把答案背下来价值就折半了。对称二叉树背后藏着一串相关知识点把这些串起来面试时就能举一反三。这里聊聊它和同构二叉树、遍历方法的关系以及一个很多人会踩的推理误区。5.1 和“判断两棵树是否相同”是姊妹题LeetCode热题100里有一道“相同的树”Same Tree题号100和对称二叉树紧紧挨着。那道题的递归函数是def isSame(p, q): if not p and not q: return True if not p or not q: return False return p.val q.val and isSame(p.left, q.left) and isSame(p.right, q.right)看到没有对称二叉树和它只差一行字比较方向。相同的树比较的是左对左、右对右对称二叉树比较的是左对右、右对左。把这个区别记住两道题一起刷效率翻倍。面试时你甚至可以主动提一句“这道题和LeetCode 100是姊妹题只是比较方向从同侧变成了交叉”这种对题型的归纳能力比会背十道题答案都亮眼。5.2 为什么不能只比较中序遍历结果有些同学刷多了遍历类题目会冒出“歪主意”树对称中序遍历结果应该是回文的吧那我只要中序遍历一遍看数组是不是回文不就行了这里藏着很深的坑。我前面提过中序遍历为回文常常和对称性同时出现但树的“值回文”不等于树的“结构镜像”。因为中序遍历只记录了节点值的访问顺序丢掉了很多结构信息。两棵完全不同的二叉树完全可能产生相同的中序序列一棵树光靠中序序列也还原不出它原本的几何形态。所以“中序回文对称”这个推理是站不住脚的。更可靠的做法永远是从根节点开始沿着镜像路径逐对比较亲眼看结构是否匹配。这也从侧面解释了为什么这道题会被放在热题100里它在提醒你树的判断问题不能偷懒依赖“序列化后比较”必须回归到结构本身。5.3 搜索二叉树和线索二叉树顺带梳理概念边界搜热词时看到“搜索二叉树”“线索二叉树”也在这道题的关联搜索里顺带帮你理一下概念边界别混为一谈。搜索二叉树BST对节点的要求是“左子树所有节点小于根右子树所有节点大于根”它关注的是值的大小关系和对称性没有必然联系。一棵搜索二叉树可以完全不对称比如所有节点都挂在右子树上的退化链。线索二叉树则是为了加速遍历而设计的它把空指针改造成指向前驱或后继的线索本质是一种存储优化手段和判断对称性更是八竿子打不着。刷题时遇到这些名词如果概念混在一起容易把解法思路带偏。我的建议是每道题的解法要牢牢锚定在一个核心定义上对称二叉树的核心定义就是“镜像节点的值相等、空值匹配”其他概念再炫也先放一边。6. 实际刷题体验与建议最后聊一点个人感受吧。我第一次刷这道题时自作聪明先写了层序遍历数组回文判断结果栽在了一个很刁钻的测试用例上后来改成递归一行通过那种“思路一旦纠正代码豁然开朗”的感觉到现在都记得。第二次刷的时候我刻意要求自己把递归、栈迭代、队列迭代三种写法都写一遍写完再模拟跑几个对称和不对称的例子整个题目才算真正刻进脑子里。如果你也在刷LeetCode热题100我建议这样安排这道题先用递归解法AC然后关掉题解自己把递归改成迭代再自己构造几个边界用例测试包括空树、单节点、两节点、三层不对称、深层单支树。这一套流程下来你对二叉树“空值判断”“镜像配对”“递归终止条件”三个基本功点的掌握会有一个肉眼可见的提升。6.1 现场手撕的一个小技巧面试时要在白板上写这题我有个个人习惯先把递归函数的三个分支写成一个注释大纲# 1. 都空 - True # 2. 一个空 - False # 3. 都不空 - 值相等且两路镜像递归成立然后把大纲对应成代码。这样一来逻辑线非常清楚就算中间写错了面试官也能看到你的思考方向。白板面试最怕的不是写错而是闷头乱写让面试官完全抓不住你的思路。6.2 关于“要不要背代码”的真心话我不建议背这道题的代码。因为对称二叉树的解法模板一旦理解你就能自然推导出来背反而容易背串。你应该背的是“镜像配对”这个模式左对右、右对左。理解了模式相同的树、翻转二叉树、判断子树这些题目都能顺着同一套思路走下去。刷题刷到最后拼的不是代码量而是模式归纳能力。6.3 再分享一个复盘技巧刷完这道题后一周可以重新做一遍但这次用另一种语言。如果你之前用Python写就试试Java或者C如果之前用递归这次强制用迭代。这种主动制造“陌生感”的复盘法比当天反复刷十遍都有用它能逼你抛弃肌肉记忆重新理解问题结构。对称二叉树是我个人很推荐用来做这种多语言复盘的题目代码短、逻辑精、回报率高。