算法训练营刷到第16天二叉树专题进入第四组打卡的时候我明显感觉到题风变了。前面几天练的基本就是前序、中序、后序、层序遍历无论递归还是迭代核心都是“把节点访问一遍”到了这一天题目开始让你用遍历去回答问题树平不平衡、根到叶子的路径怎么收集、左叶子之和是多少、最底层最左边的节点是谁、能不能找到一条和为指定值的路径。换句话说递归不再只是遍历模板而是要承担“收集信息、传递结果、控制剪枝”这些正经工作了。这篇文章就把DAY16这几道题放在一起聊聊一聊我是怎么从“会写遍历”过渡到“能设计递归”的也把我踩过的几个坑一并写出来。1. 平衡二叉树别只盯着根节点核心是把子树高度一层层带回来1.1 先分清“深度”和“高度”遍历顺序才不会选错平衡二叉树这道题第一眼看过去很好理解每个节点的左右子树高度差不超过1就行。但很多人第一次写会犯同一个错——只判断根节点的左右子树高度差不大于1然后直接返回true完全没有检查子树内部是否已经失衡。我有一个特别直观的例子一棵树的根节点左边挂了两层右边只有一个节点光看根的左右子树高度差可能不超过1但左边第二层的那个节点如果它的左右又差了一层整棵树照样不符合平衡定义。所以题目里的“每个节点”不是摆设它要求你对所有子树做同样的判断。这里要先想清楚两个概念深度是从根节点往叶子方向数的越往下数字越大高度是从叶子节点往根方向数的越往上数字越大。平衡二叉树要比较的是左右子树的高度差高度这个信息天然需要从叶子一层层传回来所以递归就应该写成后序遍历也就是先处理左右孩子再处理当前节点。如果用前序遍历走到当前节点时左右子树的信息根本还没算出来你就只能再写一个求高度的函数每到一个节点就重新往下扫一遍。看起来代码也能过小数据但一碰到退化成链表的树那就是典型的指数级重复计算复杂度直接失控。把高度信息通过后序递归带回来一次遍历就能把整棵树检查完。1.2 用 -1 做哨兵比单纯返回高度多一层剪枝我在做题时用的核心写法是递归函数返回当前节点的高度如果发现子树已经不平衡就返回 -1。这样父节点只需要检查返回值是不是 -1就能知道自己下面的某棵子树已经出事没必要再继续往下算。def get_height(root): if root is None: return 0 left_height get_height(root.left) if left_height -1: return -1 right_height get_height(root.right) if right_height -1: return -1 if abs(left_height - right_height) 1: return -1 return max(left_height, right_height) 1这段代码里有一个很容易被忽略的顺序设计先递归左子树一旦左子树返回 -1就直接 return -1右子树根本不会被执行。这不仅是省时间更重要的是避免了无意义的递归入栈。因为只要左子树已经失衡无论右子树长什么样这棵树都不可能平衡了。还有一个常见实现是把“是否平衡”作为全局变量递归函数仍然返回高度最后再判断全局变量。这种写法也能过但不够优雅。用 -1 作为哨兵相当于让返回值同时承担了两层语义正常数字代表高度-1代表“这里已经不平衡”。它在父节点那边用一行 if 就能处理代码更干净判断也更早。建议把这种“哨兵返回值”的思路记下来后面很多需要“既要信息又要状态”的递归题都能复用。2. 二叉树的所有路径递归回溯必须成对出现2.1 为什么路径收集天然适合前序遍历加一个共享路径容器求根到叶子的所有路径题目本身不复杂但它是“递归回溯”最经典的入门题。想要收集一条完整路径你必须从根节点就开始记录每往深处走一步路径就多一个节点等到叶子的时候把路径变成字符串塞进结果集。这个顺序决定了它基本只能按前序遍历来写先处理当前节点再进入左右孩子。我一开始犯过的错误是总想用后序去“把路径拼起来再返回”结果发现路径信息在返回过程中很容易丢。后来才想明白路径是“过程中”的状态不是“子树返回值”能直接表达的东西。一段比较稳的模板是这样def dfs(node, path, res): if node is None: return path.append(str(node.val)) if node.left is None and node.right is None: res.append(-.join(path)) else: dfs(node.left, path, res) dfs(node.right, path, res) path.pop()这里最关键的一行在最后path.pop()。因为 path 是同一个 list在整个递归过程中被所有分支共享你进入某个节点时往里加了一个值退出时就必须要把它拿走否则兄弟分支看到的路径会带上别人的残留节点。我把这个规则总结成一句话进入就记录离开就删除每一层递归的路径变化必须严格对称。2.2 回溯放错位置现场还原一次踩坑过程我在练习时写过一版经典的错误代码在进入叶子节点后先把路径加入结果然后直接 return没有执行末尾的 pop。当时跑单条路径全是对的一跑复杂树就出问题。比如一棵树根节点值5左边有一个叶子4右边有一个叶子6。正确结果应该是“5-4”和“5-6”两条。但因为我从左边叶子直接 return这个共享的 path 容器里还留着4的值再进右节点时路径就变成了“5-4-6”。这个坑的本质是递归 return 并不会自动帮你撤销对共享容器的修改。你必须在每一层手动让容器恢复原状。判断是不是真正理解回溯就看你能不能让 path 的变化和递归的进退完全同步。还有一个写法上的取舍递归参数里用字符串而不是数组比如 dfs(node, path - str(node.val))这样每个分支都会生成一个新字符串天然不会污染其他分支也不需要写 pop。字符串版本虽然思路更简单但频繁拼接会产生额外开销在小数据量场景下无所谓训练营里建议还是把数组加回溯练熟。因为后面你做路径总和Ⅱ这类题还是要用一个共享路径容器来回溯那才是真正考验功力的时候。3. 左叶子之和其实你该检查的是“父节点的左孩子”3.1 叶子自己看不出自己是左还是右求左叶子之和第一反应可能是递归到每个节点判断它是不是叶子如果是叶子再看它是不是左孩子。但问题是递归函数只拿到当前节点它并不知道自己相对于父节点的方位。你没法通过当前节点自身判断“我是不是左叶子”因为 leaf 的判定只能说明这是个叶子。想搞清左右关系就必须回到父节点那一层去看。所以这道题真正要写的是遍历过程中检查当前节点的左孩子是不是“左叶子”。如果当前节点的 left 不为空并且 left.left 和 left.right 都为空那这个左孩子就是我们要累加的节点。这让我想到一个更生活化的比喻你要判断一个孩子是不是家里的“长子”得先知道他的父亲是谁而不能只盯着这个孩子自己看。二叉树里的左右属性是一样的它是相对概念必须拿到父节点这一层才能判断。3.2 递归代码怎么写才能不重复、不漏算我最后用的递归很短但每一项都有讲究def sum_left_leaves(root): if root is None: return 0 total 0 if root.left and root.left.left is None and root.left.right is None: total root.left.val total sum_left_leaves(root.left) total sum_left_leaves(root.right) return total这里有一个看上去矛盾的地方如果 root.left 已经是左叶子我仍然会继续递归调用 sum_left_leaves(root.left)。有人可能会觉得这是多此一举但这样做其实很安全。因为传入的 root.left 如果是叶子节点递归进去后既不会命中“左孩子是左叶子”的条件也不会再产生新的累加最后返回0。它只是多了一层没有意义的调用不会导致重复计算。比起纠结这点小性能我更担心的是另一种写法当节点是叶子时直接返回节点值比如写if not root.left and not root.right: return root.val。这种写法会把右叶子也算进去因为叶子本身并不知道自己是左还是右只能无差别返回。很多答案初版就挂在这一点上。迭代解法其实也是一样只要你在遍历中带着“当前节点”去检查它的左孩子是不是左叶子就行。BFS、DFS、前中后序随便选只是换了一个访问方式判断条件始终放在父节点那一层。把这道题想清楚再去碰“收集左路径”“判断方向”这类题会顺很多。4. 找树左下角的值一个“从右往左层序”的小捷径4.1 反向层序遍历最后一个出队的节点就是答案找树左下角的值第一眼看容易被“左下角”几个字带偏以为就是一棵树最左边那条路径的叶子。实际上它的意思是最后一行里从左往右数的第一个节点。如果一棵树的最后一行有三个节点要返回的是最左边的那个而不是左边路径上随便一个节点。最稳妥的方法是层序遍历。常规思路是BFS一层层扫记录每一层第一个节点最后留下来的就是答案。但有个更省事的技巧——层序遍历时按照“先右孩子入队、再左孩子入队”的顺序进队也就是从右往左地遍历每一层那么最后一个出队的节点恰好就是整个树最底层最左边的那个节点。你不需要额外记录“这一层的第一个节点”只需要一个变量每次出队都更新它等队列彻底清空变量里存的就是答案。这个技巧我第一次看到时觉得有点“反直觉”所以特意用多层树推了一遍每一层都从右往左访问访问的最后一个值自然是最左侧的等所有层都访问完最后一次更新的就是最底层的最左节点。想通之后就觉得它非常顺。4.2 递归版本深度参数加“先左后右”的更新顺序层序方案虽然稳但训练营里很多同学还是会用递归写一遍因为它更贴近“从根出发逐个探索”的思维。递归写法需要引入一个全局记录当前已经到达的最大深度 result_depth以及最大深度对应的节点值 result_val。递归时带着当前深度 depth每次进入节点后如果 depth 大于 result_depth就更新 result_val并且把 result_depth 更新为 depth。这里必须强调一个顺序先递归左子树再递归右子树。因为同一个深度下我们要的是最左边的节点。先访问左子树左边一旦触发了深度更新右边再来一个同样深度的节点时由于它没有大于 result_depth就不会覆盖这样 result_val 始终保持最左侧的值。max_depth -1 result None def dfs(node, depth): if node is None: return if depth max_depth: max_depth depth result node.val dfs(node.left, depth 1) dfs(node.right, depth 1)我看过有人把“更新result”放在判断叶子节点之后这样做既麻烦又容易漏。其实不需要额外判断叶子只要深度条件满足走到哪一层就记录哪一层的节点非叶子节点即使被更新也无所谓因为后面更深的节点一定会覆盖它。唯一要注意的是根节点为空这类边界情况题目通常不会给空树但自己写测试用例时要习惯先判一下。5. 路径总和用“剩余额度”配合短路返回5.1 把目标值一路减下去比累加求和更省心路径总和这道题题目要求是找一条根到叶子的路径使路径上节点值之和等于 target。很多人的第一反应是递归时多传一个 sum 参数走到叶子时判断累加结果是否等于 target。这个思路没有错但写起来总要多维护一个变量。我更推荐把 target 当成一个“剩余额度”从根往下走的时候每次进入一个节点就用 target 减去它的值。到叶子时只需要判断剩余额度是不是刚好等于0。这样写的好处是你不需要在函数里单独维护一条路径和每一步的目标都是“还剩多少需要凑齐”判断逻辑非常直观。下面是核心框架def has_path_sum(root, remaining): if root is None: return False if root.left is None and root.right is None: return remaining root.val return has_path_sum(root.left, remaining - root.val) or has_path_sum(root.right, remaining - root.val)这个“减法思维”在很多回溯类题目里都好用。以后如果你遇到“组合总和”一类问题会发现一模一样目标值不是等到最后再比对而是沿途扣除最后用一条简单的等值判断收尾。5.2 叶子判断不能少短路返回也依赖它路径总和最常见的坑是把叶子判断漏掉。比如树只有一个根节点5target是5这时候 root 既是根也是叶子直接返回 true 没问题。但假如根节点5下面还有左右孩子target还是5你就不能因为某一步剩余值减到了0就提前返回因为题目要求的是“根到叶子”的完整路径不是停留在中间节点。所以叶子条件必须写清楚left 和 right 都为 None 时才检查 remaining 是否等于当前节点值。把“金额清零”放在非叶子节点上是这道题最容易翻车的地方。最后一行递归用or连接左右子树还有一个隐性的性能点Python 的 or 是短路运算符如果左子树已经返回 True右子树根本不会进入递归。这意味着在已经找到一条满足条件的路径时整个递归会像气泡一样迅速冒泡返回剩下的搜索全部停止。如果你想要的是“收集所有满足条件的路径”就不能用 bool 返回了得改成 void 加一个共享 list做路径收集和回溯。DAY16里后面的路径总和Ⅱ就是这种思路。两道题放一起练正好能对比“只要存在”和“要全部答案”分别应该怎么设计递归返回值。6. 把DAY16这组题装进同一个框架递归返回值的三种类型6.1 int、bool、void 分别适合解决哪类问题练完这一天我发现这五道题真正的分界线不是二叉树的遍历顺序而是递归函数应该返回什么类型。这个选择几乎决定了整道题怎么写。第一种是返回具体数值比如高度、节点个数、子树总和。平衡二叉树就是典型后序递归把左右子树的高度带上来了当前节点才能判断是否平衡并算出自己的高度。左叶子之和本质上也是返回一个数值只是这个数值表示“当前子树里满足条件的左叶子总和”它同样依赖子树的返回值往上传。第二种是返回布尔值处理“存不存在”这类问题。路径总和就是最典型的 bool 题。找到一种情况就立即停止向下搜索用 or 实现短路整棵树不用全遍历完。bool 题的难点通常是“终止条件什么时候为true什么时候为false”因为一旦判断错整个搜索过程就会提前结束或者永远找不到答案。第三种是返回 void结果靠外部容器收集。二叉树所有路径、左下角的值都属于这类递归本身只负责“走过程”真正的结果存在全局变量或者传入的 list 里。void 型递归最看重的是副作用管理比如路径容器什么时候加入、什么时候删除深度变量要不要回退这些都必须在递归的进退中保持匹配。我用下面这个表格把DAY16的几道题快速归了一下类复习时看着很清楚递归返回值解决的问题形态关键写法DAY16对应题int数值需要把子树信息汇总到父节点返回高度、总和或用-1表示异常状态平衡二叉树、左叶子之和bool布尔只问“是否存在”目标值减法短路返回路径总和void收集需要记录所有过程结果共享容器加回溯或用深度全局变量所有路径、左下角的值6.2 这组题调试时通用的三个方法练完这组题之后我养成了一个习惯只要递归代码跑出来的答案不对先不急着改逻辑而是检查三件事。第一检查空节点返回的值是不是“中性值”。在路径总和里空节点应该返回 false在高度计算里空节点应该返回0在收集路径时空节点应该直接 return。如果中性值给错了比如该返回0的地方返回了空字符串整个递归链会一路带偏。第二检查叶子节点的判断。很多二叉树题的终止条件不是“遍历完空节点”而是“走到叶子”。平衡树可以一路走到空节点路径总和必须在叶子处做最终判断左叶子更是要和父节点联动。一旦把叶子和空节点混在一起处理代码就会在答案边界上反复出错。第三打印“进入”和“退出”两行日志。尤其在递归回溯相关的题上只打印进入节点根本看不出 path 容器在离开时是否恢复原状。我会在函数开头打印 path 当前值在函数末尾的 pop 之后再次打印 path。两行日志一对比谁漏了回溯、谁多删了节点立刻现出原形。另外强烈建议每个用例都额外跑几种形状的树空树、只有根、只有左链、只有右链、左右都不平衡的树。很多代码在最简单的测试上跑得漂亮一到左链就栈溢出、一到右链就漏结果。这些边界不是为难自己而是递归题最容易在这些地方暴露设计缺陷。
