1. 项目概览Day18二叉树专题到底包含哪些东西1.1 为什么第18天的打卡要从二叉树开始我的算法打卡进行到第18天前面半个月刚把数组、链表、哈希表、双指针这类偏线性的结构刷到基本顺手今天正式进入树形结构的第一站二叉树。很多人到这一步会有一种“代码忽然变得不像代码”的感觉因为之前的题目大多可以靠循环加几个指针反复移动来解决而二叉树天然带着递归和层级两种属性代码写起来往往很短但错误藏得很深。今天的学习我没有急着堆题量而是先把二叉树的基础概念彻底过一遍再用前中后序和层序一共四种遍历方式做了两种写法的对照最后用几道经典题验证递归理解是否真的到位。这篇文章适合和我一样按计划刷题、学习进度在半个月到一个月之间的同学零基础也可以把它当成第一份树结构入门笔记来读。1.2 先统一术语根节点、叶子节点、深度和高度二叉树学习最容易翻车的地方不是代码而是概念没对齐。我建议把二叉树看成“节点和边的集合”根节点是整棵树的入口度为0的节点是叶子节点每个节点最多有两个孩子分别叫左孩子和右孩子空子树用空节点表示。刷题时更要小心“深度”和“高度”这两个词不同教材定义不一样有的是根节点深度为0有的是根节点深度为1树的高度有的按节点数算有的按边数算。我自己的习惯是默认根节点深度为1空树深度为0进入一个做题平台先看它的题目描述和示例不要拿自己的假设硬套。真正的思考单位应该是“节点”写递归函数时只考虑当前节点要做什么左右子树能返回什么不要把整棵树一次性放在脑子里。1.3 今日学习路径遍历、递归、操作、调试四步走今天我把学习拆成了四条线。第一条线是遍历包括递归版和迭代版的前序、中序、后序、层序这是二叉树所有题目的地基。第二条线是递归设计重点练习“终止条件—单层逻辑—返回值”这个铁三角把求深度、翻转、对称判断这些经典操作都归到同一个思考框架里。第三条线是层序变种从最朴素的按层输出扩展到右视图、锯齿形遍历一类问题。第四条线是调试我把自己之前犯过的低级错误整理成了一份排查清单包括空节点处理、队列大小变动、递归返回值类型不一致等。这样安排的好处是不管题目换多少层皮最后都能回到遍历和递归这两个核心点上来。2. 递归遍历的唯一套路终止条件、单层逻辑、返回值2.1 先写出口还是先写操作我的习惯是先把出口写死写递归遍历时很多新手的顺序是先把“访问节点”的操作写出来再补一个空判断这很容易漏掉终止条件。我现在的习惯是反过来开头第一行永远先处理空节点吗”会觉得非常神奇但看懂之后你就掌握了二叉树递归最重要的观察角度一个节点的整个子树可以被当作一个整体交给递归去处理。使用模板时还有几个细节需要注意。第一递归函数里的operate(root)如果只是打印返回值可以直接给None如果题目要求返回一个数组那就要让递归函数把值一层层向上传。第二前序和后序是方向感最强的两种遍历前序适合在进入子树前构建路径后序适合在离开子树后收集结果而中序的位置刚好落在左子树结束和右子树开始之间。第三不要在一个题目里来回换“首次访问、第二次访问、第三次访问”的措辞我建议就记住“前序遍历位置”“中序遍历位置”“后序遍历位置”这三个叫法很多讲解为什么这么操作只说“这是后序的特性”说不清楚因为它本质就是“等你左右子树都处理完了再回来处理当前节点”。比如求最大深度的时候你需要先知道左子树有多深、右子树有多深才能算出当前节点这个子树的高度这时候必须用后序位置。而前序位置则适合做“先把自己记录进结果再往下走”的事比如复制一棵树、序列化二叉树、从上到下打印路径都是先把当前节点放入结果再去递归左右孩子。抓住这个规律会减少背诵负担。2.4 迭代遍历显式栈写法避坑指南递归写起来顺手但面试或笔试时偶尔会被要求用迭代模拟而且递归在极端情况下也可能有栈溢出风险所以至少要把前序和中序的迭代写法练熟。前序遍历迭代很简单因为根节点先被访问所以可以先把根压栈然后弹出一个节点立刻记录再把右孩子、左孩子依次压栈。注意入栈顺序和访问顺序相反正因为栈是后进先出想先处理左子树就要最后把左孩子压进去。中序遍历迭代则要复杂一些因为必须先拿到最左侧节点所以需要用cur指针一路向左压栈直到cur为空再弹出栈顶节点记录接着把cur移到弹出节点的右子树。很多人在这一步控制不住cur的状态容易写死循环我调试时会在关键行打印cur.val和stack的长度检查指针有没有推进。有人说既然迭代这么麻烦那我干脆背代码。我不建议硬背更好的办法是先用递归写一遍再对照递归顺序去推导迭代顺序。你会在推导中发现迭代版的前序和后序其实是一对镜像关系后序可以先用一个“前序变体”记录下来最后统一反转结果。也就是先按“根、右、左”的顺序收集再把结果反转成“左、右、根”。这种方式容易写、也容易检查是很实用的技巧。当然如果想要一个统一的迭代模板可以在栈里多存一个状态位的做法入栈时按反顺序放入(node, status)每次弹出时判断状态是否已经标记为“要记录”这个模板能写清楚三种遍历但代价是每条语句的意图要理解很透不适合第一次学习就硬记。3. 层序遍历与广度优先把二维结构变成一维输出3.1 层序遍历标准模板先固定本层大小层序遍历是二叉树和广度优先思想的第一次结合也是最容易出细节问题的遍历方式。核心数据结构是队列思路是先让根节点入队然后只要队列不为空就一队一队地处理。这里最容易犯的错误是直接while queue:然后node queue.popleft()再实时len(queue)来控制本层循环结果队列在不断变化最后根本无法区层。正确做法是在开始处理一层之前先size len(queue)记录当前队列长度这个size就是本层节点的个数随后只循环size次循环里弹出节点、记录值并把它们的非空左右孩子加入队列。这样在循环过程中队列里新加的孩子不会干扰本轮处理。我写的标准代码如下from collections import deque def level_order(root): res [] if not root: return res q deque([root]) while q: level [] size len(q) for _ in range(size): node q.popleft() level.append(node.val) if node.left: q.append(node.left) if node.right: q.append(node.right) res.append(level) return res这段代码返回的是一个二维数组每一层对应一个一维数组。它最大的价值在于模板化你只要在这个for循环内部做一点变化就能解决很多层序变种题。比如要返回每一层的最大值就把level []换成维护一个max_val要返回每一层的平均值就累加后做一次除法要返回左视图或右视图就在层循环的特定位置记录节点值。我习惯把它称为“层序万能模板”建议把整个过程抄下来并自己手动模拟一遍队列的进出顺序。3.2 三个高频变种右视图、锯齿形遍历、最大宽度理解了基础模板之后可以试着变化出三个方向。右视图问题要求返回从右侧能看到的节点值本质上就是返回每一层最后一个节点所以在for _ in range(size)循环里判断当前是不是本层最后一个下标i size - 1如果是就记录到结果里。锯齿形遍历要求奇数层从左往右、偶数层从右往左最简单稳妥的办法是先按层序输出再根据层下标判断是否反转当前层。不建议真的去维护一个双端队列并从一个方向插入因为边界要判断很多次反而容易出错。最大宽度问题稍微复杂一点它要求的是“某一层最左侧节点和最右侧节点之间的距离”空节点也要算位置。通常做法是在层序遍历时给每个节点附一个位置编号根节点编号为0左孩子为2 * index右孩子为2 * index 1然后把每层第一个和最后一个编号做差再加一。队列里同时存节点和编号入队时更新编号即可。这里要注意编号可能很大即使语言里整数范围够也要养成使用相对索引的习惯也就是每层开始前先把第一个索引存下来后续都减去这个基准避免溢出。我第一次写最大宽度时忘记减去基准直接拿全局索引算在很深的全二叉树用例上爆了数字范围排查了一会儿才意识到问题。3.3 复杂度分析与常见边界情况层序遍历的时间复杂度是 O(n)因为每个节点入队、出队各一次空间复杂度在最坏情况下是 O(n)比如一棵满二叉树最后一层有约 n/2 个节点队列里会同时放进这么多节点。空间复杂度不是固定值和树的形态关系很大所以面试时如果说“层序空间复杂度和树的宽度有关”比直接说 O(n) 更严谨。边界条件上空树要特判直接返回空数组只有根节点时结果应该是[[root.val]]不要把第二层空数组也加进去。此外如果题目给的是 Node 节点而不是 TreeNode要注意它可能用children列表而不是left/right属性这种题虽然也叫层序但写法要改成遍历 children 列表本质仍是同一套队列流程。4. 二叉树经典操作的递归拆解4.1 最大深度把问题交给左右子树之后再加一求二叉树最大深度是递归思想里最干净的一道题。它要求的答案是根节点到最远叶子节点的节点数量你可以把它拆成当前这棵树的最大深度 左子树最大深度和右子树最大深度的较大值 1。递归函数的任务是返回以当前节点为根的子树的深度所以空节点返回0就足够。代码如下def max_depth(root): if not root: return 0 left_depth max_depth(root.left) right_depth max_depth(root.right) return max(left_depth, right_depth) 1初学者更容易贴着题面想“我要一路往下走数到最底层”其实更容易理解为一种自底向上的过程。为了验证我强烈建议你手动用一棵三层二叉树走一遍函数调用根节点调用左子树的递归左子树再调用它的左右孩子到叶子节点时因为孩子为空返回0叶子节点本身返回1父节点从孩子那里得到1和0所以返回2根节点左右两侧得到2和1最终返回3。这个“递归返回值逐层向上汇总”的感知一旦建立后续很多题都会顺起来。考虑时空复杂度时时间 O(n)空间最坏 O(n)当树退化成一条链时递归深度等于节点个数。4.2 翻转二叉树交换动作放在递归之前还是之后翻转二叉树是一个很经典的递归实操题基本要求是每个节点的左右孩子交换位置。表面上是“交换孩子”但深层次是“子树也被一并交换”。我见过有人写递归时先if root再立刻invert_tree(root.left)最后才交换左右孩子这会导致只有当前节点被交换子树内部没被真正翻转。正确写法是交换操作在前然后继续递归交换当前节点的左、右子树def invert_tree(root): if not root: return None root.left, root.right root.right, root.left invert_tree(root.left) invert_tree(root.right) return root其实“先递归后交换”也能写对只要先把左右子树引用存下来再去递归那两棵子树最后交换回来但明显不如“先交换再递归”直观。这道题让我认识到递归题的顺序会影响结果形态前序遍历位置做交换是自顶向下调整后序遍历位置做交换是自底向上调整大多数时候两种都能达到目的但必须保证“递归的对象是交换之后的左右子树”。做这道题时我还犯过一个很蠢的错只交换了值没有交换整个子树引用导致只有根节点的两个子节点值换了子树结构没变。所以写代码时要交换整个left/right指针不是交换val。4.3 对称二叉树两颗子树相互比较而不是单棵树递归对称二叉树问的是给定一棵二叉树检查它是否镜像对称。很多人第一反应是写一个对单棵树的递归但对称天然需要两个节点之间同时比较。更准确地说需要比较的是“左树的左孩子”和“右树的右孩子”、“左树的右孩子”和“右树的左孩子”。我实现了一个辅助函数接收两个节点如果两者都为空说明对称返回 True如果只有一个为空返回 False如果值不相等返回 False否则继续递归配对比较。def is_symmetric(root): if not root: return True return check(root.left, root.right) def check(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 check(left.left, right.right) and check(left.right, right.left)这个辅助函数里的left和right并不一定是同一棵树的左右孩子它们在递归过程中会越来越“交叉”比如比较left.left和right.right这是镜像对称的关键。以我自己的经验如果只盯着单棵树想容易陷入“遍历顺序比较前序和中序”这种绕弯的解法直接定义双参数递归思路就很直白。代码里层层返回True/False时一定要确保每个分支都有返回值初学阶段很容易在某一分支写了return None然后被当作 False 用结果测试偶尔对、偶尔错。4.4 路径总和递归参数里带上“剩余目标”路径总和类问题也很适合拿来检验递归设计。题目通常要求判断是否存在一条从根节点到叶子节点的路径使得路径上所有节点值之和等于目标值。我比较推荐的写法是递归时传入减少后的目标值每到一个节点就从目标值里减掉当前节点值当到达叶子节点时直接判断剩余目标值是否为0。如果当前节点不是叶子节点就继续往左右子树传target - root.val。def has_path_sum(root, target): if not root: return False if not root.left and not root.right: return target root.val return has_path_sum(root.left, target - root.val) or has_path_sum(root.right, target - root.val)这里的“空树返回 False”是安全出口而“当前是叶子节点”是真正的终止条件两者不能混淆。有一个常见坑是根节点左右孩子都为空也就是只有一个根节点时如果目标值等于根节点值应当返回 True如果用“当前为空节点返回 False”作为唯一出口会在叶子节点上提前终止因为叶子节点的左右孩子为空递归进去都会返回 False。所以写递归时要区分“递归终止”和“提前返回”两个概念。路径变种题还有记录路径本身那种情况需要在递归参数里维护当前路径列表并在回到上一层时做回溯也就是删除最后加入的节点如果你打算继续往后刷值得单独花一天时间练习回溯和二叉树的结合。5. 实操试错记录与排查思路5.1 我踩过的三个低级错误今天的实操过程我踩了不少坑其中三个非常典型值得单独拿出来说。第一个是忘记处理空节点。写递归遍历时我以为只要在进入递归函数的最前面写if root is None: return就够了但有时判断条件写成了if root.right is None然后在同一分支里继续调用root.right.left自然就会报错。二叉树题目里“空节点”本身不是一种异常它是递归的合法边界所有代码逻辑都要能处理它。第二个是层序遍历时用len(q)作为每层循环次数但循环体内部还在不断往队列里加子节点导致每层多处理了新加进来的下一层节点结果输出把两层混在一起。这个问题只看代码很难发现一旦用例变成满二叉树层数就乱了。第三个是递归函数返回值不统一有些分支返回一个整数有些分支直接写了return结果是None在需要累加的题目里就会出现TypeError。5.2 排查递归问题的三个调试技巧递归代码报错后不要直接盯着屏幕发呆我会按下面三个步骤来查。第一步用最简单的空树和单节点树去跑边界用例这能快速排除“出口写错”的问题。第二步在递归函数入口处打印当前节点值并缩进表示递归深度这样能看到调用顺序能判断前中后序位置到底对不对。第三步如果题目要求返回值比如最大深度我会单独用一个depth参数记录当前深度前序遍历式地更新一个全局变量再用后序返回来对照如果两种方式结果不同一定是递归条件写错了。调试时不要怕写临时打印只要在最终提交前删掉就好。递归栈比较深的时候打印输出会很多可以先限制最大深度超过某个值才打印。5.3 一份我自己常用的二叉树测试用例表在日常练习时我通常不会只拿题目示例进行测试而是自己准备一套固定用例覆盖空树、单节点、满二叉树、单支树、普通三叉多叉结构。我把它们整理成测试场景表遇到新写的二叉树函数就先跑这一套。测试场景结构特点主要验证目标空树根节点为 None所有递归入口是否安全单节点树只有根节点是否返回合理结果满二叉树每个节点都有左右孩子层序、递归深度是否正常左单支树只有左孩子一直链到底是否会栈溢出或顺序错误右单支树只有右孩子一直链到底后序遍历顺序是否正确对称二叉树左右子树完全镜像对称函数是否识别不对称二叉树结构或值不对称对称函数是否可以返回 False这个表对我的帮助很大因为很多题目只要在这些结构上跑一遍就能把边界问题暴露出来。尤其是单支树它会让递归深度达到节点数量级是最容易压栈的一个场景用来检验递归函数是否控制好空节点非常有效。6. 二叉树专题之后进阶方向与我的学习体会6.1 下一步先搞定二叉搜索树二叉树这一关过去之后随后的重点很自然地落在二叉搜索树上。二叉搜索树的中序遍历结果是有序数组这是它最重要的性质。做遍历时中序位置要非常敏感比如在二叉搜索树里找第 K 小的节点本质上就是在中序遍历过程中计数到第 K 个节点时直接返回。插入和删除节点时删除操作会比插入复杂一些因为要处理三种情况叶子节点直接删只有一个孩子就让孩子顶上来有两个孩子则要寻找左子树最大值或右子树最小值作为替补。不要急着背规则先拿一棵具体的小树走一遍删除过程把“替身节点”的选择思路理顺后面实现起来会轻松很多。6.2 我理解的递归层次从上到下写代码从下到上想结果二叉树专题学到后面我发现自己的思维方式发生了一个明显变化。刚开始写递归时我总试图按照“人的视角”从上到下模拟执行过程每走一步都要想当前节点是谁、下一层要做什么这样很容易大脑过载。后来我逐渐养成两个层次分开处理的习惯写代码时从上到下设计也就是只关心当前节点该做什么其余交给递归思考结果时从下到上分析也就是先想叶子节点的返回值再逐层向上推导。这种思考方式不仅适用于二叉树在之后学习回溯、动态规划时也会复用。刷题时如果遇到递归题目卡壳我通常不是去背模板而是先画一个只有三个节点的小树手动执行一遍函数找到返回值的汇聚点。6.3 Day18之后的个人练习计划经过今天的集中练习我对二叉树的最大感受是它没有想象中那么难但也没有想象中那么容易写对。容易的地方在于递归模板非常统一只要把终止条件、单层逻辑、返回值三者想清楚大部分题都能往下写容易出错的地方在于边界和顺序空节点处理错一个地方整棵树都会跑偏。我给自己定的后续计划是再用三天时间做二叉树的操作题比如最近公共祖先、路径总和、二叉树展开成链表这类同时每周抽出一点时间把今天写的递归模板和层序模板重新默写一遍直到它们变成条件反射。如果你也想在算法学习的旅程里征服二叉树建议不要急着比进度把四种遍历和四个经典操作的递归过程亲手推一遍比多刷十道题更有用。