如果你正在刷 LeetCode 热题 100对称二叉树这道题你大概率已经撞上了。它虽然标着 Easy但绝不是那种看一眼就会的送分题——很多人第一次写出来的代码能过样例一提交就被“运行时错误”或者“答案错误”教做人。我自己最初也挂在同一个地方递归函数写了一半发现拿 root 的左子树和右子树直接比较根本不对。这篇文章不打算只贴一份能过的代码而是把递归和迭代两种解法掰开揉碎讲清楚顺便把“写二叉树程序时为什么总是报运行时错误”这个高频问题一并解决了。适合刚开始刷二叉树的新手也适合想在热题 100 里把二叉树类型题一次性吃透的选手。先交代一下题目本身。给定一棵二叉树判断它是否沿根节点中轴线镜像对称。比如[1,2,2,3,4,4,3]这棵树就是对称的而[1,2,2,null,3,null,3]就不是。很多人第一反应是递归遍历思路方向没错但落笔时才发现陷阱全藏在“对称”两个字的语义里。1. 题目拆解与核心思路1.1 本质比较两棵子树是否互为镜像把对称二叉树这个要求翻译成自然语言根节点先不看真正要比的是“左子树”和“右子树”这两棵树是不是互为镜像。什么叫互为镜像镜像和相等是两回事。判断两棵树是否完全相同比的是p.left 和 q.left、p.right 和 q.right而判断两棵树是否互为镜像比的是p.left 和 q.right、p.right 和 q.left。这就是整道题唯一的、也是最核心的思维难点。画个最简单的例子。左子树是2 - 3这样的结构右子树应当是2 - 3但节点方向相反即右子树的左孩子对应左子树的右孩子。拿照镜子来类比你抬起左手镜子里的人抬的是右手。树也一样镜像的配对关系是交错的不是平行的。一旦在递归里把配对方向写成了“左对左、右对右”你判断的其实不是镜像对称而是左右子树完全相等这样[1,2,2,3,null,null,3]这类本应对称的树就被误判成 false 了。所以这道题的正确打开方式是定义一个新的两参递归函数check(left, right)语义是“这两棵树是否互为镜像”。接下来所有递归调用都围绕这个函数展开。1.2 为什么“单参数递归”是陷阱我见过很多人的第一版代码长这样def isSymmetric(root): if root is None: return True return isSymmetric(root.left) and isSymmetric(root.right) and root.left.val root.right.val这代码错得相当隐蔽。isSymmetric(root.left)表示“左子树自己对自己对称”isSymmetric(root.right)表示“右子树自己对自己对称”。这跟题目要求的“左子树和右子树互为镜像”完全是两码事。一棵只有左子树、没有右子树的树比如[1,2]它的左右子树各自对自己对称吗空树按定义也算对称所以这段代码可能返回 True但整棵树根本不具备镜像结构。理解了这一点就会明白为什么必须引入辅助函数。因为我们需要把“对称性”从一棵树内部的递归变成两棵树之间的递归比较。单独一个参数描述不了“镜像”这种二元关系必须有两个参数分别指向镜像两侧的节点。1.3 为什么热题 100 里一定要掌握这道题对称二叉树之所以进了热题 100不只是因为它常考而是因为它是一个绝佳的“递归模板题”。它同时考察了递归终止条件的设置、递归参数的配对方式、空指针边界处理以及迭代时数据结构的选择。这四个点恰好是二叉树类型题共通的底层能力。后面你会遇到相同的树、翻转二叉树、另一棵树的子树甚至路径总和、二叉树最近公共祖先解题套路本质上都没跑出这套框架。把对称二叉树彻底想明白等于给二叉树系列打了个地基。2. 递归实现手把手写出无 bug 版本2.1 终止条件怎么设计递归函数的骨架很简单但终止条件必须严格按顺序写。以check(left, right)为例第一反应应该是对 TreeNode 对象的None判断。如果left is None and right is None说明两侧同时为空当然对称返回 True。如果left is None or right is None说明一侧为空另一侧不为空结构上就不对称返回 False。如果两侧都不为空就比较left.val和right.val不相等直接返回 False。最后才进入递归交叉比较left.left 与 right.right、left.right 与 right.left。为什么必须先把“两边都空”的判定放在最前面因为后面用到or时是建立在“排除掉两边同为 None”的前提上的。如果不先处理全空情况直接写if left is None or right is None: return False那空节点碰到空节点也会误判为 false得不偿失。完整的 Python 实现from typing import Optional # 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 isSymmetric(self, root: Optional[TreeNode]) - bool: if root is None: return True def check(left: Optional[TreeNode], right: Optional[TreeNode]) - bool: if left is None and right is None: return True if left is None or right is None: return False if left.val ! right.val: return False return check(left.left, right.right) and check(left.right, right.left) return check(root.left, root.right)对外层root is None的特判很多人会漏掉。题目虽然没说空树算不算对称但按二叉树的一般定义空树满足对称条件所以必须返回 True。如果不做这个特判直接调用check(root.left, root.right)会对None取属性直接抛AttributeError这就是最常见的“运行时错误”来源之一。Java 版本的结构完全一致class Solution { public boolean isSymmetric(TreeNode root) { if (root null) return true; return check(root.left, root.right); } private boolean check(TreeNode p, TreeNode q) { if (p null q null) return true; if (p null || q null) return false; if (p.val ! q.val) return false; return check(p.left, q.right) check(p.right, q.left); } }2.2 为什么递归方向必须是交叉的这个问题值得再强调一遍。check(left.left, right.right)这一步是整个算法的灵魂。从结构上分析一棵树要想对称左子树的左子树就必须和右子树的右子树镜像对应左子树的右子树就必须和右子树的左子树镜像对应。这就是为什么递归参数是“左-右交叉”而不是“左-左平行”。用[1,2,2,3,4,4,3]手动推演check(root.left, root.right)中左侧节点是值为 2 的子树右侧节点也是值为 2 的子树值相等。接着递归check(2.left3, 2.right3)再递归check(2.right4, 2.left4)全部通过整棵树对称。如果写成平行方向第二次比较就会变成check(3, 3)和check(4, 4)看起来好像也能过不它会先比较左子树的左孩子与右子树的左孩子对于[1,2,2,null,3,null,3]这种经典反例左子树右孩子是 3右子树左孩子是 null平行比较时会把3 和 null放一起结果误判为 false但真正的镜像判断里左子树的右孩子对应的是右子树的左孩子同样也是 null 和 null理应判为 True。所以一眼就能看出为什么这题必须交叉。2.3 用 还是 is这道题里最容易踩的 Python 坑Python 刷题时新手最容易犯的一个错误是拿TreeNode对象直接比较。比如写if left right以为是在比较两个节点值实际上这对没有重载__eq__的 TreeNode 对象来说比较的是内存地址。两个内容完全相同的TreeNode(2)是不同的对象他俩的得到 False而同一个节点和自身比较才会 True。正确写法是if left.val ! right.val。只要涉及“节点值相等”永远通过.val比较。判断节点是否为空时推荐用is None/is not None这是 Python 社区判断单例对象的惯用方式语义清晰也避免个别自定义类覆写__eq__带来意外行为。2.4 递归版时间复杂度与空间复杂度每个节点在递归过程中最多被访问一次所以时间复杂度是 O(n)n 是二叉树节点总数。空间消耗来自递归调用栈最理想情况是平衡二叉树栈深度为 O(log n)最坏情况是树退化成一长条链表递归深度接近 n空间复杂度为 O(n)。这也是为什么有些面试官会追问一句“你能写出非递归版本吗”——不是递归不行而是他们想看你对递归深度风险的理解。3. 迭代解法队列视角彻底摆脱递归3.1 为什么要用队列成对比较理论上所有递归都能改写成迭代对称二叉树也不例外。迭代思路可以这样建立想象我们用一个队列存放“待比较的节点对”每次从队列头部弹出两个节点检查它们是否满足镜像条件再把它们的孩子节点按镜像配对规则继续入队。只要队列中所有配对都通过整棵树就是对称的。初始时把root.left和root.right作为第一对入队。这与递归版本的首次调用完全对应。Python 实现如下from collections import deque class Solution: def isSymmetric(self, root: Optional[TreeNode]) - bool: if root is None: return True queue deque() queue.append(root.left) queue.append(root.right) while queue: left queue.popleft() right queue.popleft() if left is None and right is None: continue if left is None or right is None: return False if left.val ! right.val: return False queue.append(left.left) queue.append(right.right) queue.append(left.right) queue.append(right.left) return True这里有个细节第一次popleft()取出的节点和第二层popleft()取出的节点是一对所以入队时必须保持严格成对的顺序。上面的代码按“左孩子 - 右孩子”配对入队顺序是先放left.left和right.right一组镜像对再放left.right和right.left另一组镜像对。这样在后续循环中popleft()每次弹出的两个节点总是应当互相比较的那一对。3.2 迭代写法里最容易写错的 return 位置递归版里遇到两个节点同时为空时可以直接return True因为在递归中这是整棵子树的最终结论。但迭代版里绝对不能这么做因为你只检查完队列中“当前这一对”后面可能还有待比较的节点对。举个例子一棵三层的对称树根节点检查完毕后队列里已经存入第二层的四个节点。如果第二层某个节点对比较到两个空节点时直接return True后面的第三层节点就直接被跳过了相当于只验证了局部对称。所以迭代版遇到“双方都为 None”的正确操作是continue继续从队列中取出下一对。只有当队列全部清空且没有触发任何失败条件才能返回 True。这是我见过迭代写法中出错率最高的一行值得反复提醒。3.3 栈版本与队列版本的异同把队列换成栈其实也一样能做只是配对顺序从“先进先出”变成“后进先出”比较逻辑完全没有变化。用栈的好处是代码长得更像递归展开的过程面试时如果被追问可以顺手写出来def isSymmetric(root: Optional[TreeNode]) - bool: if root is None: return True stack [(root.left, root.right)] while stack: left, right stack.pop() if left is None and right is None: continue if left is None or right is None: return False if left.val ! right.val: return False stack.append((left.left, right.right)) stack.append((left.right, right.left)) return True队列版本和栈版本的时间复杂度都是 O(n)。空间复杂度上队列在最坏情况完全二叉树的最后一层需要存约 n/2 个节点栈在最坏情况下同样接近 O(n)。两者实际区别只在于遍历顺序面试时能答出“队列做层序成对检查栈做深度优先检查”就已经够了。3.4 层序遍历视角为什么每层回文能判断对称还有一个直观但实现略繁琐的视角对整棵树做层序遍历把每一层的节点值按“空节点也占位”的方式存成数组然后判断该数组是否回文。比如第二层[2, 2]是回文第三层[3, 4, 4, 3]也是回文则对称。这个思路本身没错但实现时要处理一个问题层序遍历中必须把空节点的孩子也保留成占位符否则会丢失结构信息。当树比较深且空节点较多时数组里会塞满 None既浪费空间代码也不够优雅。队列法本质上就是在做层级成对检查但通过“成对入队”省去了显式分层是更推荐的落地方案。4. 高频报错与排查技巧实录4.1 “写二叉树程序时为什么总是报运行时错误”热词里有“写二叉树程序时为什么总是报运行时错误”这说明这是刷题群体的普遍痛点。二叉树代码的运行时错误来源非常集中绝大多数跑不出这三类。第一类AttributeError: NoneType object has no attribute left。在访问node.left、node.right或node.val之前没有判断node是否为 None。对称二叉树里最容易中招的位置就是入口处check(root.left, root.right)之前没判断root是否为空空树直接崩。第二类RecursionError: maximum recursion depth exceeded。递归基线条件缺失或者基线条件位置不对导致递归无法收敛。还有一种情况是树本身特别深比如链表型二叉树有 10000 个节点Python 默认递归深度是 1000也会炸。遇到这种场景要么调大递归深度要么直接用迭代解法。第三类逻辑错误而不是语法错误。判断节点值的时候写成了left right代码不报错但结果恒为 False。这类错误最难排查因为本地样例可能恰好让你以为代码没问题一提交就 WA。下面是排查速查表现象常见原因修复方法AttributeError: NoneType object has no attribute left对空节点访问属性入口未判空在递归函数开头先判断 None入口处特判 root 为空RecursionError: maximum recursion depth exceeded基线条件缺失或树深超过默认递归深度检查终止条件深度大的树改用队列/栈迭代提交结果恒为 False用比较 TreeNode 对象改为比较node.val空判断用is None提交结果恒为 True迭代写法在空节点处直接return True将return True改为continue全部节点检查完再返回本地正常、提交超时队列用list.pop(0)导致 O(n) 弹出使用collections.deque的popleft()4.2 本地调试技巧手写建树和可视化工具很多简单的树问题不是思路不会而是用例构造太麻烦。LeetCode 上给出的输入是一个数组比如[1,2,2,null,3,null,3]但本地调试时你得手动 new 一堆 TreeNode非常容易写错。我用得最顺手的是一个从层序数组构建二叉树的 helperfrom collections import deque from typing import List, Optional class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right def build_tree(vals: List[Optional[int]]) - Optional[TreeNode]: 根据层序遍历数组构建二叉树null 表示空节点 if not vals: return None root TreeNode(vals[0]) queue deque([root]) i 1 while queue and i len(vals): node queue.popleft() if vals[i] is not None: node.left TreeNode(vals[i]) queue.append(node.left) i 1 if i len(vals) and vals[i] is not None: node.right TreeNode(vals[i]) queue.append(node.right) i 1 return root有了build_tree测试用例就可以写成一行build_tree([1,2,2,3,4,4,3])。再配一个反转函数把树还原成层序数组方便肉眼对比结构def tree_to_list(root: Optional[TreeNode]) - List[Optional[int]]: if root is None: return [] result [] queue deque([root]) while queue: node queue.popleft() result.append(node.val if node else None) if node: queue.append(node.left) queue.append(node.right) return result这两个 helper 几乎可以覆盖二叉树刷题 80% 的本地调试场景。每次提交前至少跑五组用例空树、单节点、标准对称树、非对称树、一深一浅的树。4.3 对称二叉树题目常见的测试用例组合我建议把下面这组用例作为固定测试集任何版本的实现提交前都过一遍输入树层序数组期望结果说明[]True空树按定义对称[1]True单节点天然对称[1,2,2,3,4,4,3]True标准对称三层树[1,2,2,null,3,null,3]True注意左子树右孩子 3 对应右子树左孩子 3[1,2,2,null,3,null,null]False左右结构不一致[1,2,2,3,null,null,3]True左子树的左孩子 3 对应右子树的右孩子 3第二行到第三行的差异非常经典[1,2,2,null,3,null,3]很多人肉眼觉得不对称但它其实是对称的。你可以画一下根节点 1 的左右孩子都是 2左侧 2 的右孩子是 3右侧 2 的左孩子是 3两者恰好构成镜像。对称的定义是结构上完全镜像不看“数值是不是都在左边”这也正是递归交叉比较要解决的问题。5. 从对称二叉树扩展到整个热题 100 二叉树系列5.1 对称、相同、翻转三兄弟必须一起掌握对称二叉树不是孤立题目它和 LeetCode 上另外几道经典树题有着天然的关联。相同的树LeetCode 100判断两棵树是否完全一样递归里配对方式是p.left 和 q.left、p.right 和 q.right也就是“平行比较”。翻转二叉树LeetCode 226则是把每个节点的左右孩子交换。把翻转和相同组合起来一棵树如果翻转之后和自身相同那么这棵树就是对称的。这三道题的递归逻辑完全同构区别只是递归参数和交换动作不同。可以用一个简单的表格来整理题目核心递归逻辑解决目标101 对称二叉树check(p.left, q.right) and check(p.right, q.left)判断两棵子树是否镜像100 相同的树check(p.left, q.left) and check(p.right, q.right)判断两棵树是否完全一致226 翻转二叉树交换当前节点左右孩子后递归生成一棵镜像翻转后的树刷题时把这四道题连在一起做对二叉树递归的“参数配对”能力会有质变。你会发现所谓的变体题只是换了配对方式或增加了交换操作骨架一模一样。5.2 递归三步法对称二叉树是最好的练习素材很多教程把递归总结成“出口、逻辑、调用”三段式但抽象的描述不太好懂。拿对称二叉树为例这套方法论可以落成非常具体的步骤。第一步确定函数语义。check(left, right)干什么判断两棵子树是否镜像。这一步决定了递归参数个数和返回值类型。第二步列出终止条件。双方为空返回 True单方为空返回 False值不等返回 False。写死这三条后函数就有了确定出口不会无限递归。第三步编写当前层逻辑和递归调用。当前层逻辑是“值相等且左右交叉配对同时成立”所以用and连接两个递归调用。我刷题时有个习惯拿到题目先不写代码用文字在草稿纸上把这三步写出来。对称二叉树这道题结构不大但三步流程非常典型。把三道三步法练透后面遇到复杂递归题比如路径总和、二叉树最大路径和至少不会在下笔时大脑一片空白。5.3 我的实际练习建议最后分享一点个人体会。对称二叉树这道题我第一次写迭代版时就因为把空节点判断里的continue写成了return True在[1,2,2,3,null,null,3]这类用例上反复翻车。这种“边界条件差一行结果完全相反”的教训比任何讲解都更让人记住递归和迭代的本质区别递归是子树级的结论迭代是队列级的局部检查。如果你正在推 hot 100 的二叉树部分我强烈建议不要只背代码。把递归版、队列版、栈版三个版本都独立写一遍然后分别跑完 4.3 的测试用例集。最后再尝试用“翻转相同”的思路去实现一次看看能不能意识到这三者其实是同一个算法的不同表现形式。做到这一步对称二叉树才算真的吃透了后面刷相同的树、翻转二叉树、另一棵树的子树时你会明显感觉顺畅很多。