刷到“代码随想录Day16”这三道题——226.翻转二叉树、101.对称二叉树、104.二叉树的最大深度——的时候我明显感觉到二叉树题型的节奏开始起来了。前几天的数组、链表、哈希表大多是线性结构递归基本只在链表反转这种有限场景里用到了二叉树这儿递归变成了主力工具迭代和BFS/DFS的切换也成了日常操作。这三道题看似独立实际是同一个递归内核的不同变体翻转考的是交换左右子树的动作对称考的是比较两个子树的逻辑最大深度考的是递归收集子树信息并返回。把它们放在一起刷理解深度会翻倍。1. 三道题为什么值得放在一起刷1.1 它们共享同一个递归底座很多初学者刷二叉树的第一反应是“背模板”但模板背多了容易翻车因为二叉树题目之间的差异往往藏在递归函数的返回值和比较逻辑上。翻转二叉树要返回的是处理后的根节点对称二叉树要返回的是布尔值表示左右两侧是否相等最大深度要返回的是一个整数。这三个返回值类型完全不同正好逼着你思考“递归函数到底该返回什么”。返回节点说明你在修改树的结构返回布尔值说明你在做判断往往需要两个节点同时参与比较返回整数说明你在从子树收集状态。想清楚返回值递归函数的骨架就出来了。我在刷完这三道题之后的体会是二叉树递归题的核心其实是三件事——终止条件是什么、当前层要做什么、返回值怎么往上传。1.2 适合什么基础的同学如果你刚学完链表反转和数组二分还没接触过树这种递归结构这三道题是很好的入门组合。它们不涉及复杂的回溯、动态规划或路径记录纯粹考察最基础的DFS和BFS思维。如果你已经能独立用层序迭代解决二叉树题这三道题也能帮你把递归写法补圆。尤其对称二叉树很多人迭代能做出来递归却写不对因为拿不准该比较哪两个节点。Day16的题目编排之所以经典就是因为它从基础形态出发把一个通用能力拆成三个可练习的角度修改结构、判断结构、统计深度。把这三道题吃透后面做路径总和、二叉树最近公共祖先、重建二叉树时你会发现自己理解递归的速度明显变快。1.3 我推荐的学习顺序我的建议是先用层序遍历BFS做翻转再用层序做深度最后单独啃对称的递归。为什么不建议一上来就递归因为BFS是从根节点向下一层一层处理视觉和心理上都很直观代码也不容易越界。等层序版本写顺了你自然能体会到“从层扩展到深度”的规律再回头看递归版本时就知道递归其实是在替系统维护一个隐式栈。不过对称二叉树是例外我会比较推荐先理解递归版本再写迭代版本因为它的递归写法反而比迭代更好理解。单纯靠BFS层序遍历是没法直接判断对称的必须成对比较节点。这里面有一个很重要的认知转折二叉树问题不能只“遍历一遍”了事有时候要同时传入两个节点做比较。2. 翻转二叉树先掌握层序再去体会递归2.1 题目到底在问什么翻转二叉树的定义是对于每个节点交换它的左右子树。这个交换不仅发生在根节点而是整棵树的每个节点都必须执行相同操作。需要注意这里交换的是节点指针或子树引用不是交换两个节点的值。如果只交换值子树的内部结构并不会被翻转结果会完全错误。一个常见的困惑是翻转后的结果能不能用中序遍历验证我用过几次后来放弃了。因为翻转前的中序是左-根-右翻转后理论上应该是右-根-左但对于某些对称的树来说这两组序列可能恰好相同容易造成“翻转成功”的错觉。真正可靠的验证方法是直接在纸上画一棵不对称的树执行交换后再画一遍或者用层序输出对比左右位置。2.2 层序遍历版本每一步都看得见层序翻转的思路很直接用队列从根节点开始每弹出一个节点就交换它的左右孩子然后把存在的孩子重新入队。持续处理直到队列为空。from collections import deque def invertTree(root): if not root: return None queue deque([root]) while queue: node queue.popleft() node.left, node.right node.right, node.left if node.left: queue.append(node.left) if node.right: queue.append(node.right) return root这段代码最关键的是“交换左右孩子之后按交换后的状态做入队判断”。也就是说交换后新的左孩子如果存在就放入队列。很多人在第一次写时会习惯性地写成先记录左右孩子再交换最后把旧孩子入队。这样也不会错但容易多一行临时变量。实际刷题时可以两种都写一写体验一下变量引用在二叉树中的微妙之处。为什么层序版本适合入门因为它把复杂的递归过程拆成了一个循环。你只要保证每个节点都被取出来、交换、再入队就不要额外关心调用栈的深度。这个方法的时间复杂度是O(n)空间复杂度是O(n)因为最坏情况下队列里会存储整层节点。2.3 递归版本把交换动作“交给树自己”递归版本的核心思路是翻转一棵树等于翻转它的左子树和翻转它的右子树然后交换左右子树。def invertTree(root): if not root: return None root.left, root.right root.right, root.left invertTree(root.left) invertTree(root.right) return root如果你想追求更纯粹的“从子树收集结果”写法也可以先递归再交换def invertTree(root): if not root: return None left invertTree(root.left) right invertTree(root.right) root.left right root.right left return root两种写法里第一种更常见也更直观。但我想特别提醒递归翻转时不要用中序方式也就是不要写成“翻转左子树、处理根节点、翻转右子树”的顺序。因为在中序顺序下当你翻完左子树后根的左子树已经是翻转后的结果接着你翻转右子树时原来的右子树会跑到左边这个顺序会导致某些子树被重复翻转或翻转不对。具体来说如果写成下面的样子def invertTree(root): if not root: return None invertTree(root.left) root.left, root.right root.right, root.left invertTree(root.right) return root这其实是先翻转左子树再交换此时原右子树变成了新的左子树最后又去翻转这个“新左子树”而它实际上是没有被翻转过的原右子树看起来好像也说得通但问题在于原来的左子树被翻转后交换后变成了右子树最后一步“翻转右子树”又把它翻了一遍导致原左子树的部分节点被翻转两次。最终结果往往只在特定树形下碰巧正确。所以翻转二叉树的递归推荐使用前序先交换再递归左右或者后序先递归左右再交换不要用中序。2.4 翻转还能用栈模拟如果你不想用层序队列也可以用显式栈模拟深度优先遍历def invertTree(root): if not root: return None stack [root] while stack: node stack.pop() node.left, node.right node.right, node.left if node.left: stack.append(node.left) if node.right: stack.append(node.right) return root这个写法的思路是每次弹出节点完成交换再把孩子压栈。它和层序的区别只在于处理顺序一个是先处理同层兄弟一个是沿一条路走到黑。实际面试中你只要写出递归或层序中的一种再口头说明另一种思路即可。我自己的习惯是先写递归再补一句“如果担心递归深度可以改成层序BFS用队列交换每个节点”。3. 对称二叉树递归比较中的对称美学3.1 为什么只遍历一遍不能判断对称二叉树这道题最容易犯的错误是把它当成“左孩子等于右孩子”的简单比较。比如看根节点的左右孩子是否相等这当然不够因为对称是一种结构性约束左子树的左孩子要和右子树的右孩子相等左子树的右孩子要和右子树的左孩子相等。我一开始用层序遍历写过一个版本把每一层所有节点值收集到数组里再判断该数组是否回文。这种方式对于“完全满二叉树”可能有效但一旦某个节点缺少左孩子或右孩子空位会影响数组排列直接回文判断会误判。比如下面这棵树1 / \ 2 2 \ \ 3 3层序数组是 [1, 2, 2, null, 3, null, 3]只看值不看结构的话可能会以为它对称实际上这棵树并不满足镜面对称因为左子树的右孩子对应右子树的左孩子而右子树的对应位置是空的。所以判断对称必须在结构层面成对比较。3.2 递归版本成对比较两个节点递归判断的核心是定义递归函数compare(left, right)表示这两个节点所在的位置是否对称。终止条件要拆成三种情况左右都为空对称返回 True其中一个为空不对称返回 False两者都不为空但值不相等返回 False。如果前三种情况都没触发说明当前这对节点值相等接下来递归比较left.left和right.right以及left.right和right.left。def isSymmetric(root): if not root: return True def compare(left, right): if not left and not right: return True if not left or not right: return False if left.val ! right.val: return False return compare(left.left, right.right) and compare(left.right, right.left) return compare(root.left, root.right)这里最容易写错的地方是递归调用的对应关系。很多人在初学时容易写成compare(left.left, right.left)下意识觉得“左边的左对应右边的左”但实际上对称要求的是外侧与外侧比、内侧与内侧比。所谓外侧就是左子树的左边界和右子树的右边界所谓内侧就是左子树的右边界和右子树的左边界。这个对应关系是整道题的核心。3.3 迭代版本用队列模拟成对入队如果不使用递归也可以用一个队列模拟成对比较的过程。初始时把根节点的左孩子和右孩子一起入队。每次从队列中取出两个节点按照递归逻辑中的规则判断然后按配对顺序继续入队左孩子的左孩子与右孩子的右孩子左孩子的右孩子与右孩子的左孩子。from collections import deque def isSymmetric(root): if not root: return True queue deque() queue.append(root.left) queue.append(root.right) while queue: left queue.popleft() 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) queue.append(right.right) queue.append(left.right) queue.append(right.left) return True这个解法有一个细节因为每次都是成对弹出、成对压入所以循环体内每次popleft()两次。当遇到两个兄弟节点都为空时直接continue不要盲目往队列里加空孩子否则会死循环或把空节点无限传递。我在自己写迭代版本时踩过一次坑就是没有continue而是继续往队列添加四个空孩子导致循环无法结束。逻辑上添加空节点本身不报错但会产生大量无意义的空配对性能很差。3.4 对称二叉树的一个变体思考当你理解了compare(left, right)之后可以顺便想一想 LeetCode 上的“相同的树”这道题。相同树的比较是compare(left.left, right.left)和compare(left.right, right.right)也就是对应位置相等。对称二叉树则是外侧 vs 外侧、内侧 vs 内侧。两题的结构如此相似但比较方向截然不同。把这两题放在一起做会非常有助于理解二叉树递归中“参数位置”的意义。我刷题时习惯在一个笔记文件里画一棵三个节点的二叉树然后分别标出“相同的树”和“对称的树”各自递归比较的连线。画完之后你会豁然开朗原来所谓对称就是把其中一棵子树镜像之后看两棵树是否相同。所以还有一种解法是先翻转左子树再判断它和右子树是否相等。这个解法思路很有趣而且正好串联起今天的前两道题。4. 二叉树的最大深度DFS与BFS两种视角4.1 最大深度和最大高度的微妙关系二叉树节点的深度、高度和层数在定义上容易混淆。深度是从根节点出发往下数到当前节点的边长高度是从当前节点往下到最远叶子节点的边长层数则是深度加一。最大深度和根节点的高度其实是同一个数值所以很多题解里会说“根节点的高度就是树的最大深度”两个说法没有本质冲突。关键在于递归返回值怎么设计。用后序遍历思维写递归时我们实际上是在求“当前节点的高度”——先拿到左子树高度再拿到右子树高度取较大值加一后向上返回。最终在根节点处这个返回值就是整棵树的最大深度。def maxDepth(root): if not root: return 0 left_depth maxDepth(root.left) right_depth maxDepth(root.right) return max(left_depth, right_depth) 1这段代码只有短短几行但它是很多二叉树题目的基础。后续要做的“平衡二叉树”“二叉树的最小深度”都长得很像。最小深度稍微特殊一点不能简单把min(left_depth, right_depth) 1直接套用因为如果一个节点的左子树为空右子树不为空最小深度是右子树深度加一而不是0加一。这是题外话但值得记住。4.2 层序版本每遍历一层深度加一用BFS求最大深度非常直观每一轮先把当前队列中的所有节点都弹出然后处理下一层节点入队每当“一轮”处理完深度加一。这里必须使用当前层的节点数来控制循环。from collections import deque def maxDepth(root): if not root: return 0 queue deque([root]) depth 0 while queue: size len(queue) for _ in range(size): node queue.popleft() if node.left: queue.append(node.left) if node.right: queue.append(node.right) depth 1 return depth这段代码里size len(queue)是最关键的。它必须在for循环之前固定下来而不是在循环里动态获取len(queue)。因为随着弹出和入队操作队列长度会变化动态获取会导致一层被拆成多层处理深度计数就会出错。我测试过如果把size写在循环条件里比如用for _ in range(len(queue))在Python中range(len(queue))只会在进入循环时求值一次所以其实不会出错。但如果你的语言不是Python或者你用的是while循环就要格外小心。更稳妥的做法是显式保存size这也是面试官希望看到的规范写法。4.3 递归和迭代怎么选从刷题稳定性来看我强烈建议掌握递归写法。原因很简单简洁、不易出错、可解释性强。绝大多数面试官看到递归写法后会继续追问“你怎么避免递归栈溢出”这时候你再补充迭代版本展示出“我理解两种解法”的能力。从实际工程角度来看如果树的深度很大递归可能导致调用栈过深。Python默认递归深度限制一般在1000左右极端情况下有栈溢出风险。C和Java也有类似限制但通常更深。所以当面试官明确要求不能用递归或者树的深度可能接近极限时用BFS迭代版本更安全。今天这三道题里最大深度的BFS版本是最值得背的因为它不仅能求深度还能顺便输出层序遍历结果甚至可以做“每层最大值”“每层平均值”这类变体题。4.4 从二叉树扩展到N叉树最大深度这道题还有一个常见扩展N叉树的最大深度。思路几乎一样只是递归时不再取左、右两个子树的最大值而是遍历所有子节点取最大深度。def maxDepthNary(root): if not root: return 0 max_child_depth 0 for child in root.children: max_child_depth max(max_child_depth, maxDepthNary(child)) return max_child_depth 1这个变体看起来很简单但它强迫你理解“递归函数体内的循环”和“递归调用自身的返回值”之间的关系。如果只是做二叉树我们习惯写left_depth和right_depth两个变量到了N叉树子节点数量不固定就只能用循环加一个初始值变量来收集最大值。掌握这个写法后很多“多叉”结构的遍历问题都能顺手解掉。5. 刷题过程中一定会遇到的坑5.1 空指针递归判断顺序的隐患对称二叉树递归版本中终止条件一定要先判断“都为空”再判断“一个为空”最后判断“值不相等”。如果不注意顺序直接把left.val拿出来做比较而left为空就会抛出空指针异常。我在写代码时曾经把判断写成if left.val ! right.val: return False然后在上方只判断了if not left or not right:但这样的顺序并不完整。因为left为空但right非空时if not left or not right已经返回了False逻辑上不会进入下一步可真正的问题是你必须保证if not left and not right在前面否则当两个都为空时left.val一样会报错。所以经验是空值判断要放在最前面并且要区分“都为空”和“有一个为空”两种场景。类似的情况在翻转二叉树中不太会出现因为翻转只操作当前节点孩子为空时直接跳过即可。但在对称二叉树、路径总和、最近公共祖先这类题中空值判断是高频出错点。我建议把“树递归的终止条件三重判断”形成肌肉记忆。5.2 中序翻转导致的逻辑陷阱前文提过翻转二叉树如果用中序递归可能导致部分子树被重复翻转。很多人会问为什么前序和后序就可以偏偏中序不行我画个执行过程就清楚了。假设节点的左子树为L右子树为R。前序做法先交换L和R再分别翻转新的左右子树这时L和R各被处理一次。后序做法先翻转L和R再交换它们也是各处理一次。中序做法先翻转L再把L换到右边然后把原来的R换到左边最后翻转右边这里的“右边”其实是已经被翻过的L于是原L被重复翻转而原R因为变成了左边在最后一步没有被翻到实际上R没有被翻转。当树足够复杂时结果会非常混乱。所以面试时如果被问到“中序可以翻转吗”最好的回答是不推荐前序或后序都更安全。5.3 层序遍历中队列长度的坑不管是在最大深度还是翻转二叉树中如果你想用层序模板必须养成一个习惯每次处理一层时先记录size len(queue)。然后在循环里用for _ in range(size)控制这一层的节点数量。不要在循环内部动态改变“本层目标处理数”。我遇到过一个真实案例有一道“二叉树右视图”的题我一开始写成while queue:然后每次弹出节点最后发现输出的每一层最右节点并不对因为我没有在每层边界切分导致“最右”的定义变了。后来冷静下来先把层序遍历每一层的框架写出来while queue: size len(queue) for i in range(size): node queue.popleft() ...这个框架能解决很多层序变体题。最大深度是每层结束时depth右视图是判断i size - 1时记录节点每层最大值是遍历当前层时更新最大值。可以说BFS层序模板就是二叉树迭代题里的瑞士军刀。5.4 快速判断“对称”时误用中序数组我之前提到不要用“中序遍历数组是否回文”来判断对称二叉树。这里再补充说明一下。中序遍历结果相同并不能保证树的形状相同更不用说对称。比如上面举过的例子1 / \ 2 2 \ \ 3 3中序遍历是 [2, 3, 1, 2, 3]实际上顺序是左子树2-3再根1再右子树2-3即 [2, 3, 1, 2, 3]这显然不是回文。但也有一些更复杂的反例可能让两个不同结构的树产生相同中序序列。所以判断对称还是要老老实实做结构比较。这也引申出一个通用经验二叉树题目如果只依赖一种遍历序列做判断很多情况下都是不够的。5.5 递归深度过大的隐患Python递归默认深度限制约1000很多二叉树在刷题平台上的数据规模不会触发限制但在本地测试超深树时可能会遇到RecursionError。如果遇到这种情况可以临时增加递归深度限制import sys sys.setrecursionlimit(100000)但这不是长久之计。面试中如果被问“递归栈溢出怎么办”回答思路是改用迭代或者把递归写成尾递归但尾递归在Python中并没有真正优化。最稳妥的方案是直接切换到显式栈或队列迭代。我今天分享的迭代版本本来就是我平时真实面试时会优先写的解法。5.6 常见问题速查表问题现象可能原因解决方法翻转后某些子树方向不对中序递归翻转导致重复操作改用前序或后序递归对称判断返回错误结果比较节点对时配错了内外侧确认比较 left.left 与 right.right层序最大深度多一层循环内外层边界没有控制好每层先固定 size 再处理空节点访问属性报错终止条件顺序不对先判双空再判单空最后取值迭代对称判断死循环两节点均为空时没有 continue双空时跳过本次循环6. 我的个人体会与延伸建议6.1 刷题节奏的经验Day16这三道题我建议用一小时左右完成。不要贪快直接抄题解先自己动手写层序模板。因为层序模板不是某一道题的专属方法而是很多二叉树题目的通用底座。等到你能够不假思索地写出队列、弹出、入队这段代码再尝试递归写法你会觉得递归不过是“把顺序颠倒一下”。比如翻转二叉树层序版和递归版表面差别很大但本质上都不是从叶子开始“倒着翻”而是保证每个节点被访问到时交换其左右孩子。只是访问顺序不同一个用队列一个用调用栈。理解了这个你就不需要死记硬背了。6.2 融会贯通的方法如果时间充裕我建议把“相同的树”和“对称二叉树”放在一起做。你会发现它们在递归参数上非常相似但比较方向相反。再用“翻转二叉树”把一棵子树翻转后再去比较两棵树是否相同也可以得到对称判断的结果。这三道题的组合练习比单刷十道题更有效。我的做法是在笔记里画几个树形图手动模拟一次递归调用把每次函数参数的变化写下来。第一步先写根节点的左右孩子比较第二步写子问题参数第三步看终止条件是否覆盖所有情况。写完之后再看代码递归就会变得非常清晰。6.3 一个小工具可视化验证有时候本地调试树结构不方便我推荐一个很实用的办法把二叉树层序遍历输出成嵌套列表比如[1, [2, 4], [3, null]]这样的形式然后用 Python 的pprint打印。在翻转和对称这两道题中这个列表可以帮助你快速确认树的结构变化是否如预期。也可以写一个最简单的打印函数def print_tree(root, level0): if root: print_tree(root.right, level 1) print( * 4 * level str(root.val)) print_tree(root.left, level 1)这个函数会把树按旋转90度的方式打印出来根部在左侧右子树在上方左子树在下方。虽然不太美观但用于调试翻转结果非常直观。我刷题时经常用它检查翻转前后有没有漏掉节点或交换错方向。6.4 后续可以这样扩展把这三道题做完之后接下来值得挑战的题目包括110.平衡二叉树、111.二叉树的最小深度、222.完全二叉树的节点个数、257.二叉树的所有路径。其中平衡二叉树需要同时计算子树深度并判断左右高度差算是“最大深度”和“对称二叉树”的结合体。二叉树的所有路径则加入了回溯是递归思维的又一次升级。我自己在完成Day16后把这三道题重新打印出来贴在笔记本内页每天睡前看一遍代码结构。三天后再做一遍速度明显快了很多。刷题就是这样第一次半懂不懂第二次抓到规律第三次融入自己的思考之后遇到变体题也不会慌。最后再分享一个实用经验如果你在用某个在线评测系统提交前先想清楚题目允许的时间复杂度和空间复杂度。翻转二叉树、对称二叉树、最大深度这三道题的最优解都是O(n)时间和O(n)空间递归版本还需要额外的调用栈空间。只要你的面试回答能说清楚递归栈和显式队列的区别面试官通常都会满意。祝刷题顺利。