hot100打卡走到第12天差不多是大多数人开始心态波动的位置。前面的数组、哈希、双指针、链表虽然也烧脑但至少套路清晰一鼓作气能顶过去到了二叉树这块递归、回溯、层序、前缀和全搅在一起很多题看题解都费劲更别说两天后自己还能不能写出来。我这天把计划里的二叉树题集中刷了一遍集中处理了最大深度、路径总和、层序遍历这几类经典题。刷完之后最大的感受是二叉树题目看起来花样多实际核心就几套模板关键是理解每个模板背后的递归边界和回溯时机。这篇文章就记录一下day12的实际刷题过程、踩过的坑和沉淀下来的模板给同样在刷hot100的朋友做个参考。1. 为什么第12天要切进二叉树hot100题单的前段梯度1.1 前十天刷过的内容是怎么给二叉树铺路的如果你是按hot100题单顺序刷的前十天大概率覆盖了数组、哈希表、双指针、滑动窗口和链表这几个板块。这些内容表面上看和二叉树没什么直接关系但实际都在给二叉树打基础。数组和哈希板块核心练的是怎么快速查到一个需要的东西。两数之和那类题你要在O(1)时间内判断某个值是否出现过用的就是空间换时间。到了二叉树里路径总和III需要统计路径数量本质上也是在查某个前缀和出现过几次和两数之和的哈希思路一脉相承。双指针和滑动窗口板块练的是怎么在遍历过程中维护一个窗口状态。这个思维迁移到二叉树就是层序遍历里维护当前层的节点集合。双指针的回退、窗口的收缩和二叉树回溯里的状态恢复本质上是同一类思维。链表板块就更直接了。反转链表、环形链表这些题练的是对指针和节点关系的敏感度。二叉树不过是从单链表的一个next指针变成了left和right两个指针操作逻辑完全同源。你会操作链表节点就一定能理解二叉树的递归下沉和返回。所以到第12天你其实已经具备了刷二叉树所需的大部分基础能力。缺的只是递归这个新思维以及一套完整的遍历模板。这也是我推荐按板块推进而不是严格按题号顺序刷的原因让前面的积累在同一个板块里集中兑现效率比东一榔头西一棒子高得多。1.2 这个时间点选二叉树的三个现实理由第一个理由是最实在的hot100里二叉树题量占比很高而且大多落在中等难度档位。这些题既不会简单到让你觉得无聊也不会难到让你直接放弃正好用来完成从看得懂递归到写得对递归的过渡。第二个理由是模板复用性。二叉树可能是整个题单中模板复用率最高的板块。一个层序遍历模板能派生二叉树的右视图、锯齿形遍历、每层最大值一个递归模板能派生最大深度、直径、平衡二叉树。花一个下午吃透这些模板后面二十几道题都是在套模板边际成本非常低。第三个理由和打卡节奏有关。第12天这个位置大多数人的新鲜感刚好用尽而动态规划、图论这些真正的硬骨头还没到来。二叉树是这一时期性价比最高的训练内容思维强度够、正反馈来得快、不容易产生我是不是不适合刷题的挫败感。如果在这个时间点去碰太难的内容很可能会直接放弃整个打卡计划。2. 最大深度与路径总和递归解法的三步收敛法2.1 104最大深度递归函数定义一句话定生死LeetCode 104题二叉树的最大深度这是一道连面试官都爱用来开场的热身题。我见过很多解法有人维护全局变量有人用层序遍历数层数但最经典的还是递归做法class Solution { public: int maxDepth(TreeNode* root) { if (root nullptr) return 0; int leftDepth maxDepth(root-left); int rightDepth maxDepth(root-right); return max(leftDepth, rightDepth) 1; } };这段代码一共五行但想真正吃透需要理解三件事递归函数定义、终止条件、单层逻辑。我把这个方法叫三步收敛法所有二叉树递归题都能用这个框架去套。第一步定义递归函数的意义。这里 maxDepth(root) 表示以root为根的树的最大深度。这个定义一定要想清楚因为后续所有递归调用都是围绕这个定义展开的。第二步终止条件。如果传入的节点是空指针那么这棵子树的高度是0直接返回。这是让递归收敛的出口漏掉它就会无限往下钻。第三步单层逻辑。当前节点的深度等于左子树深度和右子树深度中较大的那个再加上1本身。这句话听起来像废话但它是递归能成立的关键它把求整棵树深度这个任务缩小成了求两棵子树的深度。我比较推荐这种返回值风格的写法而不是在递归过程中维护全局变量去更新最大值。返回值风格天然是后序遍历逻辑自洽不需要额外引入状态变量也不需要考虑恢复现场的问题。如果用全局变量写法函数返回类型只能用void代码看起来很热闹但实际上是在绕着弯子做事容易在复杂题目里把自己绕晕。一个直观类比你让人事部统计全公司部门人数人事部不会挨个去数每个人而是让每个小组组长先统计各自小组人数再汇总。每个组长也不知道全公司多少人只需要知道自己小组多少人然后上报。这就是递归的分而治之。2.2 112路径总和叶子判定不是简单的null检查LeetCode 112题路径总和要求判断是否存在一条从根节点到叶子节点的路径使得路径上所有节点值之和等于目标值。递归代码如下class Solution { public: bool hasPathSum(TreeNode* root, int targetSum) { if (root nullptr) return false; // 当前节点是叶子节点 if (root-left nullptr root-right nullptr) { return targetSum root-val; } // 递归检查左右子树目标值减去当前节点值后传下去 return hasPathSum(root-left, targetSum - root-val) || hasPathSum(root-right, targetSum - root-val); } };这道题最大的坑在边界条件上。你注意第一行空节点返回false而不是返回targetSum 0。很多人第一次写都会写成if (root nullptr) return targetSum 0;这个写法初看好像没问题但实际会误判一类情况。要理解为什么不行得先明确题目要求路径必须从根节点到叶子节点叶子节点是指没有子节点的节点。如果你把空节点当成合法终点那么在一棵树只有左子树、没有右子树的情况下程序会沿着空的右分支走下去然后把空节点当成一条正常路径的结束点来判定。但这条路径根本不存在它没有真的走完任何一个叶子节点。我拿一棵简单的树举例根节点值为5左子节点为4没有右子节点目标值是3。正确结果是false因为5加4已经超过3了而且左子节点4不是叶子。但如果你用空节点当终点程序会先判断根节点5不是叶子然后递归右子树右子树是空直接返回targetSum 0此时targetSum传入的是3减5等于负2不等于0返回false这一侧没问题。但如果目标值改成5根节点5不是叶子递归右子树空传入targetSum为0空节点返回true于是判定存在合法路径。这就完全错了——你找了一条根本不存在的路径。所以正确的终止条件必须明确判断当前节点是否为叶子。叶子判定的标准是左孩子和右孩子都为空而不是节点为空。这道题也是我day12标记为黄的一道题看题解之前我对空节点的处理没有想透考试环境下这种错误很难自己debug出来因为小数据集里表现往往正常一旦遇到单侧子树场景就会翻车。另外注意一个细节这里用的是减法传递targetSum - root-val往下传而不是在递归里维护一个累加变量。减法传递的好处是不需要额外加参数也不用回溯恢复累加值配合叶子判断更加自然。从根一路减到叶子如果最后减到零并且到了叶子就说明存在这条路径。3. 层序模板、回溯路径和前缀和day12实际踩过的三个雷3.1 层序遍历的size快照问题LeetCode 102题二叉树的层序遍历要求按层从左到右输出节点值。这道题在hot100里属于基本功但实现时有一个细节非常容易错我先给出标准模板vectorvectorint levelOrder(TreeNode* root) { vectorvectorint res; if (root nullptr) return res; queueTreeNode* q; q.push(root); while (!q.empty()) { int size q.size(); // 关键先钉住当前层的节点数 vectorint level; for (int i 0; i size; i) { TreeNode* cur q.front(); q.pop(); level.push_back(cur-val); if (cur-left) q.push(cur-left); if (cur-right) q.push(cur-right); } res.push_back(level); } return res; }这个模板的核心就一句话在遍历每一层之前必须先用int size q.size()把当前层的节点数保存下来然后用这个固定值做for循环。为什么必须这样因为队列是动态变化的。你在for循环里每pop一个节点都会push它的左右孩子进来队列的size会持续增长。如果你不保存快照直接在for循环条件里写i q.size()那每一轮循环开始前q.size()都在变大循环次数会超出本来的层节点数导致层与层之间的节点混在一起。我第一次写的时候就是用for (int i 0; i q.size(); i)结果输出全乱了一层的数据被硬生生拆进两层。这个错误在代码评审里很难被一眼看出来因为逻辑看起来完全没问题只有跑起来才能发现队列在偷偷扩容。层序模板的重要性不仅在于这一道题。二叉树的右视图、锯齿形层序遍历、每层最大值、填充next指针全都是在这个模板上改一行两行。day12把这个模板刷熟等于同时预演了五道题。还有一个细节值得提内层for循环完成后level这个临时vector会被push_back进结果集然后下一轮重新创建一个空的level。这个每层新建一个容器的习惯很好避免手动clear带来的脏数据问题。3.2 路径总和II的path引用陷阱LeetCode 113题路径总和II要求返回所有满足条件的路径。这道题比112多了一个收集路径的需求核心操作是回溯。代码我这样写class Solution { public: vectorvectorint pathSum(TreeNode* root, int targetSum) { vectorvectorint res; vectorint path; dfs(root, targetSum, path, res); return res; } void dfs(TreeNode* root, int rest, vectorint path, vectorvectorint res) { if (root nullptr) return; path.push_back(root-val); rest - root-val; if (root-left nullptr root-right nullptr rest 0) { res.push_back(path); // 注意这里 } dfs(root-left, rest, path, res); dfs(root-right, rest, path, res); path.pop_back(); // 回溯恢复现场 } };这道题我踩过的坑说出来你可能觉得不过如此但实战中真的会让人卡半天res.push_back(path)这一行在C里会自动拷贝一份path的副本所以是安全的。但如果你习惯性地把path定义成成员变量或者用全局vector然后res.push_back(path)存的是同一个对象的拷贝这个问题不出现真正的坑在Python版本里非常致命。Python版本如果直接res.append(path)存进去的是同一个列表对象的引用。随着递归继续后续的path.append和path.pop会修改这个列表的内容等到递归全部结束后res里所有元素都变成了同一个被反复修改过的列表最后全被清空输出一片空白。解决办法是res.append(path[:])强制拷贝一份快照。这类问题的本质是引用 vs 值。C里vector作为局部变量push进结果时通常按值拷贝问题不大但一旦涉及指针、引用或全局变量就必须考虑我存的东西之后还会不会被改动。另外说下path.pop_back()这行。回溯的核心思想是你在递归入口处往path里放了一个值递归返回时必须把它取出来否则兄弟分支看到的path里多了一个不属于自己的节点。我习惯把这个过程想成钉钉子与拔钉子进入一个节点时钉下一颗钉子离开这个节点时必须拔掉否则后人来的时候会以为这颗钉子也是自己钉的路径记录就会错乱。有人可能会问那我传参的时候直接传拷贝每个分支都复制一份path不就不用回溯了吗功能上确实成立但代价是每次递归都要拷贝整条路径空间复杂度从O(height)退化成O(n*height)。在路径长、节点多的场景下这个开销会变成性能瓶颈。所以回溯恢复现场才是正解。3.3 路径总和III从暴力到前缀和的降维打击LeetCode 437题路径总和III是hot100里二叉树板块的一个小魔王。题面要求统计路径和等于目标值的路径数量但路径不要求从根开始也不要求在叶子结束只要方向向下即可。看到任意起点、任意终点很多人的第一反应是暴力把每个节点都当作起点往下DFS一遍统计所有能凑出目标值的路径。这个思路没问题复杂度是O(n^2)在树比较小的时候也能跑过。但hot100的测试集显然不是吃素的一旦遇到链式树或者接近链式的大树每个节点都要往下遍历平均O(n)的深度整体直接TLE。这就是day12我刷得最久的一道题。暴力解法写了没多久就超时之后才想到前缀和这个优化方案。前缀和的思路是这样的对于从根到当前节点的路径记录一个累计和cur。如果在之前的祖先路径中存在某个节点的累计和为 cur - target那么从那个节点的下一个位置到当前节点这一段路径的累计和正好等于target。路径的数量就等于 cur - target 这个值在祖先前缀和中出现的次数。这个思路很像数组里和为k的连续子数组那类题。数组场景里我们用哈希表记录前缀和出现的次数树场景里只要在DFS过程中维护前缀和哈希表就能做到O(n)复杂度。代码如下class Solution { public: int pathSum(TreeNode* root, int targetSum) { unordered_maplong long, int prefix; prefix[0] 1; // 空路径的累计和为0 return dfs(root, 0, targetSum, prefix); } int dfs(TreeNode* root, long long cur, int target, unordered_maplong long, int prefix) { if (root nullptr) return 0; cur root-val; int cnt prefix[cur - target]; prefix[cur]; int leftCnt dfs(root-left, cur, target, prefix); int rightCnt dfs(root-right, cur, target, prefix); prefix[cur]--; // 回溯恢复现场 return cnt leftCnt rightCnt; } };解释几个细节。为什么prefix[0] 1因为当 cur 恰好等于 target 时cur - target 0表示从根节点到当前节点的整条路径本身就是一条合法路径。哈希表里需要默认记录空路径的累计和0出现了一次否则这条路径会漏掉。为什么cnt prefix[cur - target]要放在prefix[cur]之前因为当前节点自身不能作为自己的祖先如果先自增再查询会把以当前节点为起点同时以当前节点为终点的情况也算进去路径长度变成0明显不符合要求。必须先查询再更新。为什么最后要prefix[cur]--因为哈希表记录的是当前递归路径上的前缀和。不同子树之间的路径不能互相穿越左子树统计完如果不把左子树贡献的 prefix 计数减掉右子树在查询时会把左子树的路径也算进去答案就会偏大。这和113题path.pop_back()的逻辑完全一样都是恢复现场。暴力解法和前缀和解法的时间差距在数据量上来之后是肉眼可见的。我实测过一棵节点数5万左右的二叉树暴力写法跑了接近3秒前缀和写法不到20毫秒。虽然LeetCode的测试数据未必这么极端但O(n^2)的隐患始终在能一次写对前缀和就不要给自己留超时的机会。4. 复杂度与数据范围递归栈、队列内存和暴力TLE的真实边界4.1 三题的时空复杂度实测对比day12这几道题做完我顺手整理了一张复杂度对照表方便直观感受不同解法的差异题目推荐解法时间复杂度空间复杂度104 最大深度递归后序O(n)O(height)102 层序遍历BFS队列O(n)O(n)最坏为最后一层节点数112 路径总和递归前序O(n)O(height)113 路径总和II递归回溯O(n)O(height)不计输出结果的存储437 路径总和III前缀和哈希O(n)O(n)哈希表最坏存n个前缀和437 路径总和III暴力枚举起点DFSO(n^2)O(height)这里的O(height)值得多说一句。height是树的高度在完全二叉树里约等于log n在退化链表树里等于n。所以二叉树递归题的最坏空间复杂度其实是O(n)不是很多教程里轻描淡写的O(log n)。道理很简单如果树退化成一个只有左孩子的长链递归深度就一路捅到底每层递归都要占用调用栈空间。实际刷题时LeetCode的测试集很少把递归深度压到爆栈的程度。1000层的调用栈在现代OJ默认栈大小下通常没问题上万层也还在多数平台的承受范围内。真正应该警惕的是某些平台默认栈空间较小或者你在面试现场白板手写时被问到如果栈深度太大怎么办。4.2 递归栈溢出刷题时的常见误读网上有一种说法流传很广二叉树题尽量不要用递归因为会栈溢出。我在day12的实际体验是这个说法在刷题场景下基本属于过度担忧。LeetCode这类平台二叉树的数据量一般控制在10^5节点以内退化成链表也就是10^5层递归深度大多数平台的默认栈都能扛住。反倒是你为了躲避递归去手动模拟显式栈写出的迭代版本又长又难调反而更容易出bug。那栈溢出在什么场景下会真实发生第一生产环境的服务进程栈大小有严格限制刷题和工程是两个赛道不能混为一谈。第二递归写成了死循环比如终止条件永远无法触发或者递归参数没有向边界推进。第三每次递归里复制了大数据结构比如我前面提到的传拷贝path写法虽然空间复杂度不会爆栈但大量内存拷贝会让程序变慢变卡。所以day12我对复杂度的态度是先保证逻辑正确再关注复杂度级别。只有在暴力解法明显超时的题型比如437_path_sum的暴力枚举里才需要提前把优化方案想清楚。递归栈的深度问题在hot100这个量级的数据下很少成为真正的瓶颈。5. 打卡模板沉淀与错题标记day12之后怎么复习5.1 二叉树高频模板的沉淀清单刷完day12我最大的收获不是AC了多少题而是总结出了一套可以直接套用的二叉树模板清单。这里分享给同样在刷hot100的朋友第一类递归遍历模板。二叉树的先序、中序、后序遍历本质都是同一个递归框架只是处理当前节点的时机不同。104最大深度、110平衡二叉树、543二叉树的直径全都可以归到这一类。看到需要某种以子树为单位的聚合信息优先想递归后序。第二类层序BFS模板。queue加size快照的那套写法覆盖102层序遍历、199右视图、103锯齿遍历、637每层平均值。看到按层处理的需求直接用这个模板。第三类递归回溯模板。113路径总和II、257二叉树的所有路径核心是path的入栈、递归、出栈三步操作。看到收集所有路径的需求优先想回溯。第四类前缀和哈希模板。437路径总和III是代表题数组版本是和为K的子数组。看到统计路径和等于目标值的数量且路径可以从任意节点开始优先想前缀和。把这些模板用自己的话重新写一遍、存在自己的笔记里远比抄一遍题解有效。我个人的标准是脱离题解只看题目描述能写出模板结构才算真正沉淀下来了。5.2 我的错题三级标记法与隔天复习节奏打卡不能只做加法还要做整理。我给自己定了一个三级标记法day12刷完顺手就把今天这几道题标了一遍标绿的是当场独立写出且完全理解的题。今天104最大深度和102层序遍历就是这个级别。这类题不需要反复刷隔一周看一眼模板就够了。标黄的是AC了但边界理解不够透彻的题。112路径总和就是典型我代码能过但最初对空节点的处理没有想明白是看了题解才确认要返回false。这类题隔天必须重写一遍重点检查边界条件是否能完整解释。标红的是看了题解或者思路方向不对的题。113路径总和II的引用陷阱、437路径总和III的前缀和思路都是这个级别。这类题在当天晚上就要重写一次隔一天再写一次隔一周再看一次才能确保真正消化。复习节奏上我习惯用当天晚上、隔一天、隔一周三个检查点。当天晚上重写趁热打铁隔一天验证短期记忆隔一周验证是否形成了长期记忆。如果隔一周还能秒写出完整解法这道题就可以从错题本里毕业了。我第12天晚上做完这套整理心里反而很踏实。因为我知道今天踩的坑、总结的模板之后刷二叉树的右视图、锯齿遍历、路径总和的其他变体时都会反复用到。打卡的意义不在于当天打了多少卡而在于这些模板和标记能让你后面的每一天都稍微轻松一点。