1. 先搞清楚力扣hot100第34题在考什么1.1 题目描述与对称的定义力扣hot100题做到第34题是“对称二叉树”。题目本身非常经典给一棵二叉树的根节点 root判断这棵树是不是轴对称的。力扣原题编号是 101很多公司面试也喜欢拿它当热身题。输入参数是一棵已经构造好的二叉树根节点返回值是布尔值表示整棵树是否对称。什么叫轴对称不是把左子树和右子树简单比较就行。轴对称是说以根节点为中心画一条垂直虚线树的左半边和右半边沿这根线对折后节点位置和值要完全重合。举个例子层序数组[1,2,2,3,4,4,3]表示的一棵树是对称的而[1,2,2,null,3,null,3]就不是因为根的左子树里有一个右孩子 3而根的右子树里“应该与之对应的左孩子”是空的。这里要特别留神对称比较的是“镜像位置”不是“同一位置”。第一次做这道题的人很容易觉得“递归比较 root.left 和 root.right 就行了值相等就对称”。这个直觉方向是对的但差一个关键细节比较的时候不是拿左子树的左孩子去比右子树的左孩子而是拿左子树的左孩子去比右子树的右孩子。这是整道题的核心也是面试官最想看到的点。1.2 为什么这道题能进hot100hot100基本上覆盖了各类型的“母题”对称二叉树属于二叉树递归里的高频模型。它看起来简单但能把递归、迭代、结构对比、空节点处理全考一遍。而且这题的“坑”藏得很深代码写出来可能只有十几行但每一步都值得展开讲。很多公司喜欢在面试里用它来区分“背题的”和“真正理解树的”。我自己的感受是这道题光是递归写法还不够。面试官经常会追加一句“如果不用递归你能写出来吗” 所以刷这题不能只满足于AC要把迭代写法也吃透。另外这题还牵扯到两个经典思路递归函数的“语义设计”和空节点是否入队。这两个点覆盖了二叉树题目里很大一部分通用难点刷透这一题后续很多树题都会顺手很多。2. 递归解法最直觉的做法里藏着一个关键设计2.1 递归函数的入参到底应该传几个节点很多人第一版是这样写的def isSymmetric(self, root): if not root: return True return self.helper(root.left, root.right)写到这里思路没问题但 helper 到底怎么写关键在于helper 接收两个节点而不是一个节点。因为“镜像对称”永远是一对节点之间的关系只有单个节点时你没法表达“左子树的左孩子 vs 右子树的右孩子”这种跨子树关系。我打个比方。你站在镜子前左手对应的是镜子里你的右手。判断一个人左右对称不是只看左右手位置还要看左肩和右肩、左腿和右腿的对应关系。树也一样根节点下面的两棵子树各自展开时比较路径要“交叉对应”。所以递归函数里的两个参数 a 和 b分别代表当前正在比较的两个镜像位置节点。只要这个参数设计对了后面的递归体基本就是顺水推舟。如果只传一个节点比如在递归里只判断当前节点的左右孩子是否相等你会很快发现逻辑漏洞它只能看到同一棵子树内部的左右关系而无法跨越两棵子树做交叉比较。对称性恰恰是两棵子树之间的交叉关系所以辅助函数必须有两个入参。2.2 递归终止条件与判断顺序写递归先写终止条件。这里不是只有一个终止条件而是三个并且顺序不能乱两个节点都为空对称返回 True。一个为空另一个不为空不对称返回 False。两个都不为空但节点值不同不对称返回 False。两个都不为空且值相同继续递归比较 a.left 和 b.right同时比较 a.right 和 b.left。顺序为什么重要因为如果先访问a.val而 a 本身是 None直接抛空指针。所以要先用前两个条件把空节点的情况全部处理掉再谈值。第三个条件其实也可以放在递归调用里用and连接但显式写出来更清晰面试时也更容易解释。这里还有一个容易忽略的小点递归时不是return isMirror(a.left, b.left) and isMirror(a.right, b.right)而是a.left 对 b.righta.right 对 b.left。方向反了就是判断“两棵子树是否完全相同”不是“是否互为镜像”。建议在纸上画一棵不对称的树快速用方向反的代码跑一下立刻就能看到问题。口诀其实就六个字左对右右对左。2.3 递归实现代码与复杂度用 Python 写最简洁的版本是这样class Solution: def isSymmetric(self, root: Optional[TreeNode]) - bool: def isMirror(a: Optional[TreeNode], b: Optional[TreeNode]) - bool: if not a and not b: return True if not a or not b: return False return (a.val b.val and isMirror(a.left, b.right) and isMirror(a.right, b.left)) if not root: return True return isMirror(root.left, root.right)这个代码的时间复杂度是 O(n)因为每个节点最多被访问一次。空间复杂度是递归调用栈的深度也就是树高平衡树是 O(log n)二叉树退化成链表时最坏 O(n)。力扣上直接提交没问题但如果本地测试一棵很深的树Python 默认递归深度约 1000可能出现RecursionError。这个我们放到后面常见问题里细说但至少要知道递归解法不是没有代价的。3. 迭代解法把对称判断变成两两配对的过程3.1 为什么面试官喜欢追问迭代写法递归虽然好写但递归本质上是把比较状态压在系统栈里。面试官追问迭代主要是想看两件事第一你是否清楚递归写法的调用过程第二你能不能自己用显式数据结构模拟这个过程。二叉树的迭代遍历一般用栈或队列。对称判断不是普通遍历它需要同时维护两个位置的节点所以“成对处理”是核心。我习惯用队列因为每次从头部出队两个节点再把下一对需要比较的节点从尾部入队整个过程非常直观。你甚至可以把它理解成“两个人同时从根节点附近出发一个往左走时另一个往右走保证每一步都站在镜像位置”。这两个人写下来的路径必须严格对应否则树就是不对称的。迭代解法本质上就是把这个过程机械地执行完不需要系统栈帮忙只要自己拿一个队列记录“下一步还要比较哪些位置”就行。3.2 队列的入队顺序与配对规则迭代版本最关键的坑是入队顺序。初始化时把 root.left 和 root.right 作为第一对节点入队。进入循环后每次弹出两个节点 a 和 b依次判断如果 a 和 b 都是空说明这个镜像位置两边都没节点继续。如果 a 和 b 中只有一个为空说明结构不对称直接返回 False。如果 a 和 b 都存在但值不同返回 False。如果值相同继续把下一层要比较的节点按“左对右、右对左”的顺序入队。具体入队顺序是a.left, b.right一对a.right, b.left一对。注意这个顺序和递归里的配对完全一致。如果写成a.left, b.left/a.right, b.right那就变成判断“相同树”了。提示空节点也要入队。这是迭代法里面最容易翻车的地方。很多人写层序遍历时习惯跳过 None但这里 None 代表“这个位置没有节点”是树结构的一部分。如果跳过像[1,2,2,null,3,null,3]这种不对称输入会被误判成 True。用手推一下[1,2,2,3,4,4,3]的队列变化初始队列是[2,2]弹出第一对 2 和 2值相同于是依次把左孩子的左孩子 3、右孩子的右孩子 3、左孩子的右孩子 4、右孩子的左孩子 4 放入队列。下一轮弹出 (3,3)再弹出 (4,4)全部相等返回 True。推完一组数据你对入队顺序会理解得更扎实。3.3 用 deque 实现迭代版本Python 里用collections.deque最合适因为需要从头部 popleft。代码from collections import deque class Solution: def isSymmetric(self, root: Optional[TreeNode]) - bool: if not root: return True q deque([root.left, root.right]) while q: a q.popleft() b q.popleft() if not a and not b: continue if not a or not b or a.val ! b.val: return False q.append(a.left) q.append(b.right) q.append(a.right) q.append(b.left) return True这里有几个细节。第一队列里永远存放成对的节点所以 popleft 两次是安全的。第二if not a or not b or a.val ! b.val这一行把三种失败情况合并了但一定要先判空再取a.valPython 的or短路保证了这个顺序。第三如果不想让空节点占队列也可以入队(a.left, b.right)这种元组弹出时直接拿一对代码逻辑一样只是可读性更强。用栈替代队列也可以把deque换成普通列表每次从末尾 pop 两个节点入栈顺序保持配对即可。栈和队列的区别只是遍历顺序不同不影响对称性判断因为对称判断不依赖“先处理哪一层”或“按层推进”只依赖“每一轮弹出的两个节点是否在镜像位置上”。4. 复杂度、边界条件与hot100同类题串联4.1 时间与空间复杂度再盘点很多人在面试时会说“递归 O(n)迭代 O(n)”但空间复杂度不一定说准确。给出一张表解法时间复杂度空间复杂度适用场景递归O(n)最好 O(log n)最坏 O(n)思路清晰适合快速写迭代队列O(n)最坏 O(n)避免递归深度限制面试追问用迭代栈O(n)最坏 O(n)和队列等价看个人习惯为什么递归空间是 O(log n) 到 O(n)因为递归栈深度等于树高。平衡二叉树高度约 log n退化成链时高度就是 n。迭代版本要把一层的节点成对放进队列队列在某一时刻最多存放“当前所有待比较节点”最坏情况是一棵完全二叉树的最后一层节点数量级也是 O(n)。时间上无论是递归还是迭代每个非空节点都会被访问一次空节点也会被成对检查一次所以总次数是 O(n)。不要被“空节点入队”吓到它最多让操作次数翻倍属于常数级区别不影响渐进复杂度。面试时这样说一般不会有人挑毛病。4.2 空树、单节点和结构差异输入边界条件也是面试官喜欢问的点。空树是不是对称的按力扣定义空树返回 True。单节点也返回 True因为没有左右子树可比天然对称。比较麻烦的是“节点值全相同但结构不对称”的用例。比如[1,2,2,3,4,4,3]对称。[1,2,2,null,3,null,3]不对称。[1,2,2,3,null,null,3]对称。[1,2,2,null,3,3,null]这个看起来有点绕左子树的右孩子是 3右子树的左孩子是 3结构对称返回 True。写代码前自己列出这几组用例把所有判断逻辑跑一遍比直接提交更稳。我常用的办法是先在纸上画出树结构标注镜像配对线如果配对线上两端的值能一一对上答案就是 True。这个动作花不了十秒但能避免很多“思路对了却写错方向”的尴尬。4.3 和“相同的树”“翻转二叉树”串起来看对称二叉树不是孤立题目。它在力扣 hot100 里跟另外两题关系非常近100. 相同的树判断两棵树是否完全一样递归比较的是p.left与q.left、p.right与q.right。226. 翻转二叉树把一棵树的左右子树交换。101. 对称二叉树判断一棵树的左子树和右子树是否呈镜像关系。甚至有一种解法思路先翻转根节点的右子树再复用isSameTree(root.left, flippedRight)来判断。虽然实现上多了一次树的修改但这个角度很适合用来理解对称的本质。刷 hot100 时把这三题放在同一天做你会发现递归函数的“语义设计”是共通的每一层递归返回什么、下一步该比较哪两个节点想清楚之后代码自然就写出来了。面试中还可能问“如果树里有大量重复值怎么办”答案不变值相同只是其中一个条件结构不对称照样返回 False。这也提醒我们比较顺序里“空节点判断”要放在“值比较”前面因为结构问题优先于值问题。5. 常见错误与排查技巧实录5.1 只比较了根节点的左右孩子我见过很多第一次写这题的人代码长这样def isSymmetric(self, root): return root.left.val root.right.val这种写法连第二层节点都没递归显然不对。稍微聪明一点的会递归比较左右孩子但方向写反变成判断“相同子树”。常见解释是“只要左右子树相同树就对称”这个说法不准确。对称要求的是左子树的左孩子对应右子树的右孩子而不是右子树的左孩子。遇到不对称用例就会暴露问题。排查方法很简单用[1,2,2,3,4,4,5]这类值乱序的用例去跑。如果是判断“相同树”它会返回 False但实际这棵树也不对称所以可能误打误撞通过。更有效的用例是[1,2,2,3,3,null,null]左子树左右孩子都有值右子树只有左孩子有值结构不对称但方向写反的代码可能返回 True。5.2 递归比较方向搞反方向错误的核心原因是没有建立“镜像坐标”概念。用坐标表示可能更清晰把根节点看作原点左子树的右孩子可以记作(-1, 1)右子树的左孩子记作(1, -1)。对称比较的是横坐标取反、纵坐标相同的位置。递归里对应关系就是a.left对b.righta.right对b.left。我见过有人写成这样return (a.val b.val and isMirror(a.left, b.left) and isMirror(a.right, b.right))这个写法其实是100. 相同的树的递归逻辑不在对称二叉树里用。如果发现提交后只挂少数用例大概率是方向问题。可以打开力扣调试逐层打印当前比较的两个节点值立刻能看到是“位置没对上”。5.3 迭代法没有把 None 节点入队这是我第一次写迭代版本踩的坑。层序遍历写多了看到 null 习惯性跳过结果对称判断直接变形。原因是二叉树的层序数组里null 不是“没有节点”那么简单它表示“这个位置没有节点”是结构信息的一部分。跳过 null 后下一层的节点会错位可能被当成另一棵子树的节点来比较。错误的写法大概是if a.left: q.append(a.left) if b.right: q.append(b.right)这样一旦某个位置缺少子节点队列里就少了一个元素后续配对全部错乱。正确的做法是无论节点是否为空都按配对规则入队。出队时两个都空就继续只有一个空就返回 False。这样代码看似多存了空节点但逻辑才是最严谨的。如果担心队列里有大量 None 浪费空间其实没必要None 只是一个很小的对象引用而且队列长度本来就是 O(n) 级别。5.4 根节点为空导致空指针代码第一行如果直接写return isMirror(root.left, root.right)root 为 None 时直接崩溃。正确做法是开头先判断if not root: return True或者直接写return not root or isMirror(root.left, root.right)这个写法利用了 Python 的短路求值root为 None 时不会执行后面的递归。不过为了可读性我还是习惯显式if。面试时写显式判断不容易被挑刺。5.5 本地调试工具函数刷二叉树题最烦的就是在本地构造测试数据。我写了一个简单的从层序数组构造树的工具函数放在自己的刷题脚本里。这里给一个简化版from collections import deque class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right def build_tree(values): if not values: return None root TreeNode(values[0]) q deque([root]) i 1 while q: node q.popleft() if i len(values) and values[i] is not None: node.left TreeNode(values[i]) q.append(node.left) i 1 if i len(values) and values[i] is not None: node.right TreeNode(values[i]) q.append(node.right) i 1 return root有了它就能直接跑root build_tree([1,2,2,3,4,4,3]) print(Solution().isSymmetric(root))注意 build_tree 里要跳过 None 节点但数组里 None 的位置要保留索引 i 每次仍然要递增。这个小工具对后续刷所有二叉树题都很有用建议直接加到自己的刷题模板里。6. 我刷这道题的一些实测经验6.1 两种解法在面试中的定位我的建议是先把递归解法讲到烂熟再练迭代。递归解法的优势是代码短、语义清楚适合在面试一开始快速给出方案迭代解法则在面试官问“能不能不用递归”时拿出来。实际面试中能把迭代版本里的空节点入队逻辑讲清楚比单纯背代码加分很多。有一次我模拟面试对方让我现场分析为什么不能跳过 None 节点。我用了“错位”这个词并举了[1,2,2,null,3,3,null]的例子对方明显满意。所以刷这题时不要只记代码要准备一个自己能讲清楚的反例。这种“反例原因修正”的叙述方式在面试里非常实用。6.2 调试二叉树问题的通用方法除了工具函数我还习惯在递归函数里加临时打印。比如def isMirror(a, b): print(a.val if a else None, b.val if b else None)然后用最小用例跑一遍观察比较顺序是否符合“左对右、右对左”。调试完删除打印即可。这个习惯帮我改掉了很多“凭感觉写递归”的毛病也让我对递归调用过程有了更强的直觉。如果是在力扣网页上调试其实不用本地打印直接把错例手动跑一遍、在关键分支上打断点效果也一样。关键是别急着提交先自己推演一个不对称的例子。很多时候返回 True 的误判不是值的问题而是结构问题打印节点值能立刻暴露两个节点是不是被放错了位置。6.3 一道题变一类题刷hot100的正确姿势对称二叉树这个题本质上是在训练“定义递归函数语义”的能力。isMirror(a, b)的语义是“以 a 和 b 为根的两棵子树是否为镜像关系”。语义一旦定下来递归体就是跟着这个语义走镜像意味着a.left和b.right镜像a.right和b.left镜像。我后来做相同的树、翻转二叉树、另一棵树的子树都用的是同一套思路。hot100里很多题都是这样表面是不同题目底层是同一个母题的不同变体。把对称二叉树吃透不只是会做一道题而是把“树形递归怎么设计”这件事想明白。在我实际刷题的过程中最值钱的不是记住这十几行答案而是在错了几次之后终于知道该用什么样的视角去看递归树。这个视角才是hot100真正想训练的东西。
查询的优化实战)
