第十五天算法训练营刷到二叉树的中段。LeetCode 110、257、404、222这四道题排在一起标着难度分别是简单、简单、简单、中等但把它们当成一套组合题来刷你会明显感觉到这一阶段和前面十天刷遍历时的差别题目开始要求你带着目的去递归了。平衡二叉树考你对高度的理解方式和剪枝设计二叉树的所有路径是回溯的第一次正面接触左叶子之和逼着你换一个视角看树完全二叉树的节点个数则是利用数据结构性质做复杂度优化的典型。这篇文章把四道题从头到尾拆开讲包含完整思路、可运行的代码、复杂度推导和我在实际练习中踩过的坑给同样在刷这组题的朋友做个参照。1. 第十五天的题量安排与知识定位1.1 从“遍历”到“解题”的关键转换前面的训练内容基本上围绕四种遍历方式展开前序遍历、中序遍历、后序遍历、层序遍历再加上几道经典递归题比如求最大深度、最小深度、判断对称树。到第十五天题目难度并没有突然拔高但考点变了——不再仅仅要求你把树完整走一遍而是要求你在遍历过程中做筛选、做记录、做汇总。比如所有路径要求在遍历时保存一条完整的链左叶子之和要求在遍历时筛选满足特定条件的值完全二叉树的节点个数要求你不遍历也能算出数量。这种从“访问所有节点”到“带着业务条件访问节点”的转变是二叉树刷题的第一个分水岭。很多人在这几天会有一种错觉觉得题都见过、套路都熟悉结果一提交就漏洞百出。原因其实就是前面的遍历题太“安全”了递归写好基本就过了而这四道题需要你在递归返回值、终止条件、状态恢复这些细节上做设计稍有不慎逻辑就对不上。1.2 四道题互相补充的知识模块110平衡二叉树的核心是递归返回值的双用既要返回子树高度又要标记是否失衡。257的核心是回溯和路径记录。404玩的是视角转换站在父节点去判断左叶子。222则考验性质挖掘利用完全二叉树左右子树高度关系把规模减半。四道题覆盖了递归设计的三个层面返回什么、什么时候收手、怎么消除向上传递的副作用。把它们放到同一天练比单独刷效果更好因为你会在四道题之间看到同一套递归思维的四种变体这种对比带来的理解深度是单刷十道同类题也换不来的。1.3 难度评价中的陷阱LeetCode 上110、257、404都标为简单但绝大多数第一次刷的人都会卡在细节上。110容易在终止条件上写错257容易在回溯时忘掉移除节点404容易把自己绕进“左子树里的叶子”这句话。真正刷下来你会发现难度标签只能说明思考路径不长不代表实现没有坑。这套题的实操时间我建议按1.5小时到2小时来安排宁可把代码写慢一点把每一处的递归返回值含义写注释也不要赶进度。后面刷路径总和、构造二叉树这类题时你会回来感谢这天的慢。2. LeetCode 110 平衡二叉树一次后序遍历完成判断2.1 题目本质与暴力思路的问题平衡二叉树的定义是每个节点的左右子树高度差不超过1。注意是每个节点不是只看根节点。要在根节点判断整棵树是否平衡就必须先知道左右子树是否平衡而要判断左右子树是否平衡又得知道更下面子树的信息。这天然适合递归。最容易想到的思路是自顶向下对于一个节点先分别计算左右子树的高度比较差值然后递归判断左子树和右子树是否平衡。这个做法是正确的但效率很差。计算高度本身是递归遍历而外层又在每个节点上重复计算一次高度。以一条链为例计算每个节点的高度都要走到叶子总时间大约是O(n^2)。我在本地用长度为1000的链测过暴力解法明显慢几个量级在LeetCode上虽然也能过但属于碰运气。真正面试的时候这种解法大概率会被追问一句“能不能优化”。2.2 后序遍历的高度与-1哨兵自底向上的方式只需要一遍遍历。既然是先知道左右子树的结果再决定当前节点怎么处理自然选择后序遍历。这里的关键设计是递归函数返回什么常规思路是返回当前子树的高度。但还有一类需求是“这棵子树不稳了赶紧往上报”。因为合法高度永远是非负整数用一个负数当哨兵完全可行-1就是最常用的。于是递归逻辑变成左子树返回-1说明左子树不平衡直接返回-1右子树同理左右都平衡再检查高度差最后返回当前节点高度也就是左右较大者加1。用-1做哨兵的好处是省掉一个额外布尔标记判断条件也会简单。缺点是它依赖“高度不可能为负数”这个约定看代码时需要知道这个隐式规则。如果你更在意可读性也可以返回一个二元组比如(is_balanced, height)但在递归深度栈上会多占一点空间而且判断语句会更啰嗦。我平时写题用-1写工程代码用二元组看场景决定。class Solution: def isBalanced(self, root: Optional[TreeNode]) - bool: def dfs(node): if not node: return 0 left_height dfs(node.left) if left_height -1: return -1 right_height dfs(node.right) if right_height -1: return -1 if abs(left_height - right_height) 1: return -1 return max(left_height, right_height) 1 return dfs(root) ! -12.3 代码的边界与易错点第一个易错点是终止条件。空节点的高度是0这个必须写在最前面。有人会写成返回True或者False那整个递归的返回值类型就乱了。第二个易错点是递归返回的数值含义。有人会写成“返回左右子树的节点数之差”把高度差和节点数差混在一起这在某些测试用例下会得到错误答案因为平衡定义用的是高度不是节点多少。第三个易错点是剪枝时机左子树已经不平衡时右子树就不用再跑了直接返回-1。这样可以省掉一半甚至更多的递归调用对不平衡的大树提速非常明显。我见过一种写法是先用一个全局变量记录是否平衡然后照常递归遍历整棵树。这种写法也能过但不够干净。既然递归函数本身就能把不平衡状态传上去就不需要额外维护一个外部状态少一个变量就少一份出错的可能。2.4 手写验证的测试用例我建议本地至少跑这样几组空树返回True单节点返回True根节点左右高度差为2的三层树返回False链式结构“左右交替”的不平衡树返回False以及题目示例中那个经典的[1,2,2,3,3,null,null,4,4]这个用例能有效查出错把“子树平衡”当“整棵平衡”的写法。为什么特意提这个用例因为它前面的节点都满足高度差为1只有到了第四层才暴露失衡很多粗心的实现会在这一层挂掉。3. LeetCode 257 二叉树的所有路径回溯与路径收集3.1 为什么路径题要用前序遍历输出要求非常明确从根到每个叶子的完整路径用箭头连接。这里不能后序遍历因为你收集路径时需要知道“当前走到了哪个节点”。前序遍历的顺序是“先处理当前节点再进入子树”这样路径列表天然就是根到当前节点的顺序。你可以尝试中序或者后序会发现收集到的路径要么顺序错乱要么需要额外反转很别扭。说白了路径是“根先出发一路往下”的记录只有前序遍历贴合这个语义。这类题后面还会以各种形式出现比如求根到某个目标节点的路径、求路径总和等套路都一样前序遍历加上回溯。3.2 回溯的本质走到头要退回来计算机在递归时只知道往下走。当递归返回时路径列表如果不做处理就会保留着访问过的节点导致下一分支的路径里混入上一分支的记录。想象成走迷宫时手里拿一根绳子进入新岔路时绳子放长一截退回来时必须把放长的绳子收回否则下一次走的路径就会被这根多余的绳子污染。在递归实现里“放长绳子”是对应的path.append(...)“收回绳子”是path.pop()。两个操作必须成对出现写在同一个递归函数里。很多人第一次接触回溯会觉得抽象其实核心就是这一句话递归前做了什么递归返回后就要撤销什么。不撤销的话状态是叠加的后面的分支都会拿到脏数据。这题练的就是这个基本功。3.3 两种常见的递归写法对比第一种是共享路径列表加显式回溯class Solution: def binaryTreePaths(self, root: Optional[TreeNode]) - List[str]: res [] if not root: return res def dfs(node, path): if not node: return path.append(str(node.val)) if not node.left and not node.right: res.append(-.join(path)) else: dfs(node.left, path) dfs(node.right, path) path.pop() dfs(root, []) return res第二种是每次传入新的列表副本不需要popclass Solution: def binaryTreePaths(self, root: Optional[TreeNode]) - List[str]: res [] def dfs(node, path): if not node: return new_path path [str(node.val)] if not node.left and not node.right: res.append(-.join(new_path)) return dfs(node.left, new_path) dfs(node.right, new_path) dfs(root, []) return res两种写法都能过。区别在于空间显式回溯版共用一份路径列表递归深度是树的深度h额外空间O(h)传值拷贝版在每一层都复制一遍列表对于一条链来说会产生O(n^2)的累计空间。第一种写法理解成本略高但它才是回溯的一般形态。后面做路径总和、组合、排列这些题全都依赖“共享状态加显式回退”这套模式所以我在训练营第十五天建议直接把第一种写法练熟。3.4 细节什么时候收获结果路径题最怕的错是在不该收获的时候收获。收获结果的唯一条件当前节点是叶子也就是左右孩子都为空的节点。注意不要再往叶子下面递归了。在有显式回溯的版本里我把append放在递归入口处这样根节点也会被加入路径然后判断叶子叶子就生成结果非叶子就走左右孩子最后统一pop。这样所有分支的路径都正确。还有一种写法是进入节点时先判断空再判断叶子再分别递归左右逻辑一样只是pop的位置要注意别漏掉。另有一个边界如果二叉树为空直接返回空列表。如果只有根节点路径是“1”这正好对应叶子判断才收获结果的逻辑不需要额外特判。写过递归的人应该都有体会特判加得越多代码越容易出乱子能靠逻辑本身覆盖的边界就别手工处理。4. LeetCode 404 左叶子之和换个视角看叶子4.1 “左叶子”到底是什么左叶子是指“是左孩子、并且本身是叶子”的节点。一个节点是叶子意味着它没有孩子它还得是别人的左孩子。这里有个天然的信息不对称你站在一个节点上只能看出它自己是不是叶子但看不出它在父节点眼中是左还是右。所以解题必须换一种思路站在父节点这边检查“我的左孩子是不是一个叶子”。很多人看到“左叶子”这三个字会条件反射去找整棵树偏左的节点然后越写越乱。关键是要把判定条件写清楚存在左孩子左孩子没有左右儿子满足这两个条件时左孩子的值就是贡献值。注意贡献的值是左孩子的值不是父节点的值也不是左右子树返回值的简单相加。这个细节看似废话但提交记录里写错的人真不少。4.2 递归设计在双层判断中累加递归遍历整棵树在每个当前节点判断一次如果当前节点的left存在且left的左右孩子都不存在把left.val加入结果。然后继续递归left和right。这个设计的好处是视角一致每个节点都负责判断自己的左孩子递归下去覆盖整棵树。写法上要注意不能只把递归结果return掉。例如class Solution: def sumOfLeftLeaves(self, root: Optional[TreeNode]) - int: if not root: return 0 ans 0 if root.left and not root.left.left and not root.left.right: ans root.left.val ans self.sumOfLeftLeaves(root.left) ans self.sumOfLeftLeaves(root.right) return ans这个函数返回的是“以当前节点为根的子树的左叶子之和”。每一层都先处理自己这一层的左叶子判断再叠加左右子树的递归结果。递归的返回值设计比较直观不会有歧义。4.3 另一种带标记的写法除了站在父节点判断也可以给递归函数加一个isLeft参数表示这个节点是不是作为左孩子被访问到。叶子节点且isLeft为True时返回它的值其他情况继续递归。这种写法好处是思路直观不需要在每个函数里额外判断“父节点的左孩子是否为叶子”坏处是递归调用多了一层参数且对空节点、根节点等边界情况要多加小心。我个人比较推荐第一种写法但它确实没有第二种写法那样容易一眼看明白所以我把两种都放在这里对比读者可以选一种练习。从训练营的角度讲第二种写法适合用来理解“递归参数不只是节点本身还可以带上额外的上下文信息”这件事后面做路径总和、二叉树的序列化等题目时这种带附加参数的递归很常见。4.4 这题最容易被忽略的测试用例根节点也算吗不算。如果根节点没有父节点它不是任何人的左孩子。例如只有根节点的树答案是0。又例如[3,9,20,null,null,15,7]9是左叶子7不是答案是9这个用例能检查你有没有把左子树的叶子全部算进去。还有一个容易出错的用例是[1,2,3,4]4是左叶子它的父节点2不是叶子所以2本身不能贡献但需要在递归2时判断出4这个左叶子。其实这题真正想考的不是“会不会遍历”而是“会不会从父节点视角看问题”。只要理解到这一层代码基本不会写错。5. LeetCode 222 完全二叉树的节点个数把性质变成复杂度优势5.1 普通解法的复杂度瓶颈最直接的写法数节点就是递归遍历一遍class Solution: def countNodes(self, root: Optional[TreeNode]) - int: if not root: return 0 return 1 self.countNodes(root.left) self.countNodes(root.right)这是标准答案吗是正确答案但时间O(n)、空间O(h)。如果树有千万个节点这就是千万次递归调用。题目没说节点数量级但既然专门考“完全二叉树”显然希望你不要满足于这个通用解。有人会觉得O(n)已经很快了为什么要优化因为完全二叉树是一种非常特殊的结构它的形状是确定的一定可以靠公式算出一大部分节点数。当数据量级达到很大时O(log^2 n)和O(n)的差距是数量级的。面试场合写这段优化代码明显比直接遍历更能体现你对数据结构的理解。5.2 完全二叉树的两个关键性质完全二叉树有一个决定性特征除了最后一层上面的所有层都是满的最后一层的节点都靠左连续排列不会出现右边有节点而左边空缺的情况。由这个特征可以推出一个重要结论从根节点出发左子树的高度要么等于右子树的高度要么比右子树多1。不可能出现左子树比右子树矮的情况。如果左子树高度等于右子树高度说明最后一层已经延伸到了右子树那么左子树一定是满的。如果左子树高度比右子树多1说明最后一层只铺到了左子树范围右子树一定比左子树矮一层此时右子树整层是满的。这就是判断“哪边是满的”的依据。这两个性质理解清楚了代码逻辑就顺了。核心思想一句话每次确认一半子树是满的用公式直接算剩下一半递归往下算。5.3 满子树节点数用位运算直接算高度为h的满二叉树节点数等于2^h - 1。如果左子树满且高度为dl那么“左子树 根节点”的节点数是2^dl也就是1 dl。剩下的另一边继续递归算。同理右子树满且高度为dr时先加上“右子树 根节点”的节点数1 dr再递归算左子树。为什么不用内置的pow或**因为位移运算不调用浮点库速度更快在算法题里也更直观。遇到2的幂优先写1 n已经是刷题圈里的常见习惯。注意运算符优先级1 dl和1 dr都要加括号吗看你的写法如果在表达式里混着加减建议加括号避免写成1 dl 1这种被解析成1 (dl 1)的坑。5.4 完整实现与复杂度推导class Solution: def countNodes(self, root: Optional[TreeNode]) - int: def get_depth(node): depth 0 while node: node node.left depth 1 return depth if not root: return 0 left_depth get_depth(root.left) right_depth get_depth(root.right) if left_depth right_depth: return (1 left_depth) self.countNodes(root.right) else: return (1 right_depth) self.countNodes(root.left)每次递归规模减半深度差为0时递归算右子树规模约为n/2深度差为1时递归算左子树规模也约为n/2。每层递归调用get_depth需要沿着左边界走到最底完全二叉树的高度是O(log n)所以每层代价O(log n)。一共O(log n)层总时间O(log^2 n)。这个优化在n大时优势明显比如节点数大约100万O(n)要做约100万次运算O(log^2 n)大概只有400次左右。5.5 边界与陷阱这里的else分支实际上覆盖了left_depth right_depth的情况。严谨地说完全二叉树不会出现left_depth right_depth但简单写else也没毛病能处理异常输入。另外get_depth必须一直沿左孩子走。有人会把“当前节点向右子树延伸几次”当成高度那是完全不同的含义。用位运算还有一处细节当子树高度为0时1 0等于1代表“根节点自己”数值是对的。这个边界值得注意避免写成1 depth 1这样括号错位的式子。我在本地调试时特意跑了一个单节点用例确认递归能正常返回1才提交。6. 四道题串起来的三个方法论6.1 递归函数返回值决定一切四道题写完后你会发现递归函数“返回什么”是最重要的决策。110返回子树高度用-1表示失败257的递归不返回值只修改外部结果404返回左叶子之和222返回子树节点个数。返回值设计好了整个逻辑就顺了返回值得含糊后面全在打补丁。一个实操建议动笔前先把注释写上比如“返回以node为根的子树高度若不平衡则返回-1”然后再写递归主体。我在第7章还会专门说这个习惯因为它真的是我刷题效率提升的关键。6.2 前序和后序怎么选判断顺序的直觉边往下走边做决策的比如收集路径、找目标路径用前序需要先知道子问题的答案再汇总的比如判断子树是否平衡、计算子树节点数、统计子树里的左叶子用后序。404是例外它用前序也行因为每个节点只做判断不依赖子结果但我采用自顶向下的写法是因为判断条件在父节点。判断顺序的核心原则是父节点需要什么信息就决定在什么时候访问子节点。如果把这个问题想透了后面做二叉树的最近公共祖先、最大路径和这类题时会省很多力气。那些题的本质就是“我需要子节点给我什么信息然后我怎么处理”。6.3 刷题节奏和手感养成这一天的题量其实不小我建议采用“两遍过”的策略第一遍只看题目自己憋半小时卡住了看题解思路然后默写代码第二遍合上题解直接在白板上写完整实现跑测试用例。不要只做一遍就觉得完事了。第二遍才是真正把递归返回值、回溯时机、复杂度推导这些细节刻进肌肉记忆的时刻。第十五天还是能把四道题控制在两个小时内的这个节奏对于后面刷路径总和、构造二叉树这类更复杂的题目会很关键。7. 我踩过的坑常见错误排查与一个小技巧7.1 四道题的高频错误速查表题目典型错误原因正确做法110把子树高度差写成节点数差混淆高度与节点量每层只算高度用abs比较110空节点返回True终止条件写错空节点返回0257结果出现重复多余的路径回溯时没有popappend与pop成对出现257单节点树结果为空叶子分支未处理叶子也要先append再收获404统计时把父节点值也算进去误加root.val加的是root.left.val404漏掉嵌套左叶子只判断了根节点附近递归覆盖左右子树222数满子树时仍遍历所有节点没利用满二叉树公式用1 depth直接算222get_depth走的是右链误以为高度是向右一直向左走这张表是我实际刷题过程中一条条记下来的不是凭空总结。刷到后期我还会偶尔返回来翻尤其是每次写回溯题卡住的时候看看257这一行提醒自己append和pop要成对。7.2 本地调试专用工具层序转数组刷二叉树的题最烦的就是一把测试用例眼睛看不出来对错。我习惯写一个把二叉树转成数组的小工具做对比层序输出末尾的空节点去掉再打出来。比如[1,2,2,3,3,null,null,4,4]这样的用例直接打印树的层序数组一眼就能看出来结构是不是自己想要的。这个工具在验证110、257这几道题时非常好用。代码核心就十几行队列做层序遍历遇到空节点记录None最后修剪末尾的空值。如果你也在刷链式结构强烈建议先把这个工具放进自己的代码片段里。本地调试的效率提升非常明显尤其当你在递归里改来改去的时候有一个能可视化树结构的工具比猜错强太多。我这里也顺手分享一个简单版本def tree_to_list(root): if not root: return [] res [] q [root] while q: node q.pop(0) if node: res.append(node.val) q.append(node.left) q.append(node.right) else: res.append(None) while res and res[-1] is None: res.pop() return res7.3 一个改变我写递归习惯的提示我后来养成了一个很小的习惯递归函数的开头不先写代码而是先写一句话注释说明这个函数返回什么、什么时候停止。比如“返回以node为根的子树高度若失衡返回-1”。写注释的过程倒逼我把语义想清楚很多写着写着发现逻辑矛盾的情况都被这个习惯避免了。训练营第十五天之后我刷题效率明显变高这个注释习惯比任何技巧都管用。尤其是在110这种“返回值同时承担多种语义”的题目里不写注释特别容易乱。你回头看一眼自己三天前写的递归代码如果还需要想半天才明白返回值是什么那说明当时注释没写够。把语义钉死在注释里调试和复习都会轻松很多。这四道题刷完之后我个人最大的体会是二叉树递归的瓶颈从来不是语法而是“有没有想清楚每一层递归到底在做什么”。想清楚了代码自然就顺了。哪怕过了很久再回头看注释和结构都还在复习成本也很低。如果你今天正卡在某一题上不妨先停下来把返回值注释写出来再往下走。