今天刷的是二叉树专题题目分别是 111. 二叉树的最小深度、222. 完全二叉树的节点个数、110. 平衡二叉树。这三道题放在同一天刷是有道理的它们都建立在树的遍历基础上但又各自扣了一个容易踩坑的细节最小深度不能照搬最大深度完全二叉树可以用定理加速平衡二叉树要小心重复递归的复杂度陷阱。我刷完一遍最直观的感受是这几个题不仅是练递归更是练“怎么在递归里控制返回值的语义”。如果你还没做过二叉树建议先把前序遍历、后序遍历和层序遍历写熟练再来看这三道题。如果你已经会最大深度那套递归了那更要小心最小深度里面藏着一个非常经典的误判逻辑我身边很多人包括我自己第一次都栽在那里。至于完全二叉树节点个数从O(n)优化到O(log n * log n)那个思路值得反复品。平衡二叉树则是把后序遍历玩出花的典型题。接下来我按思路拆解、代码实现、常见问题三个部分来写尽量把每一步为什么这么设计讲清楚也把刷题时真正容易翻车的点列出来。1. 内容整体设计与思路拆解1.1 三道题串联起的核心知识线先看整体。这三道题表面上是三个不相关的问题其实它们有一条非常清晰的主线都依赖树的高度或节点统计而这个高度和统计又依赖递归遍历的返回值传递。111 最小深度本质是找从根到最近叶子节点的最短路径核心是叶子判定。222 完全二叉树节点个数本质是子树计数通用做法是后序遍历累加进阶做法是利用完全二叉树本身的结构特性。110 平衡二叉树本质是判断任意节点左右子树高度差是否大于1核心是高度汇总和后序回溯。把它们连起来看你会发现代码套路高度相似都是先算左子树再算右子树然后根据两边结果做逻辑判断或数值返回。区别只在于返回的是什么最小深度返回层数节点计数返回数量平衡判断返回高度或者是-1。这就是同一天安排这三道题的意义让你在一次练习里把“后序遍历返回值”这个模型彻底吃透。后序遍历本身不难难的是搞清楚“当前节点要向上返回什么”以及“遇到什么情况要提前终止”。1.2 为什么这三道题适合放在同一天刷我的理解是这三道题恰好覆盖了递归函数设计的三个层次。第一层是直接递归节点计数就是最典型的“把问题拆成左子树右子树自身”的模式没有任何额外条件适合建立肌肉记忆。第二层是条件递归最小深度不能无脑用min(left, right)因为当一个子树为空时另一侧的深度才是有效答案这逼迫你去想清楚边界。第三层是状态剪枝递归平衡二叉树如果只用自顶向下重复求高度复杂度会退化到O(n^2)。必须让递归在发现不平衡时立刻返回失败标记这就是剪枝。这个思想在后续很多题目里都会遇到比如判断是否是对称树、是否是完全二叉树都能用类似的自底向上标记法。所以这一天与其说是刷了三个题不如说是把一个核心模型升级了三回。代码量不大但收获密度很高。2. 核心细节解析与实操要点2.1 最小深度别把最大深度的套路直接套用最大深度怎么写很多人会直接写return 1 max(maxDepth(root.left), maxDepth(root.right))最大深度没问题因为空节点返回0max会把空分支自动过滤掉。但最小深度如果把max改成min就是错误的。为什么给你一个最直观的例子一棵只有右子树的树根节点只有右孩子。此时左子树为空min(0, 右子树深度)会算出0结果就变成了1但实际上最小深度应该是2根节点到右子节点这条路径。问题出在“叶子节点”的定义上。最小深度一定要找到叶子节点也就是左右孩子都为空的节点。如果某个子树不存在那条路根本不算一条完整路径你不能把“空”当成深度0去参与比较。所以正确写法是分情况讨论左右孩子都为空当前节点就是叶子返回1。只有左孩子继续往左走返回1 左子树的最小深度。只有右孩子继续往右走返回1 右子树的最小深度。左右都有返回1 min(左右子树的最小深度)。这个题用层序遍历反而更符合直觉。层序遍历是逐层扫过去的我第一次遇到叶子节点时返回当前层数一定是最近叶子节点的深度。因为BFS天然就是广度优先一层一层往下走第一个遇到的叶子必然深度最小。我建议两种写法都练一下。递归用来巩固后序思想BFS用来理解“为什么最早碰到的叶子一定是最短路径”。2.2 完全二叉树节点个数通用遍历到按定理优化先明确一下定义完全二叉树是除了最后一层可能不满以外其余每一层都是满的并且最后一层的节点都靠左排列。通用解法没有任何难度就是遍历所有节点数一遍O(n)。确定完通用解之后就要思考一个问题题目既然专门给了“完全二叉树”这个条件能不能利用它做得更快关键定理如果一棵完全二叉树的左子树和右子树高度相等那么整棵树是满二叉树。满二叉树的节点个数可以直接用公式 2^h - 1 算出来h是树的深度。如果左右高度不等那就拆开递归根节点占1个加上左子树的节点数加上右子树的节点数。等等这里有一个细节可能有人会问到完全二叉树下左子树高度一定大于等于右子树高度但左右高度相等的情况意味着最后一层被完全填满了。这是完全二叉树结构保证的所以这个判断不会漏。复杂度分析每一次递归总会有一个子树是满的可以直接用公式返回所以每层只需要向下走一边实际是 O(log n * log n)。因为递归的深度是O(log n)每次算高度又要花O(log n)所以总体就是O(log n * log n)。这里要特别提醒一个点求子树高度的时候只要沿着最左侧一路走就行因为完全二叉树的最左侧路径长度就是树的高度。如果写通用高度函数也没错但会浪费掉这个题目给出的特殊条件。2.3 平衡二叉树自顶向下与自底向上的选择平衡二叉树定义是每个节点的左右子树高度差都不超过1。注意这里是“每个节点”不只是根节点。最直觉的写法是自顶向下对每个节点都算一次左右子树高度然后递归检查左右子树是否平衡。isBalanced(root) abs(height(root.left) - height(root.right)) 1 isBalanced(root.left) isBalanced(root.right)这个写法逻辑是对的但性能很差。原因很简单height()要从当前节点一路计算到底对每个节点重复算高度导致大量重复遍历复杂度退化到O(n^2)。更好的方案是自底向上也就是一次后序遍历同时完成两件事一是计算当前子树的高度二是判断当前子树是否平衡。只要发现不平衡直接返回一个失败的标记不再继续向上算。常见哨兵值写法是如果子树平衡返回该子树实际高度如果发现不平衡返回-1。上层只要看到左子树返回-1或右子树返回-1就立刻判定整棵树不平衡也返回-1。这个写法的核心思想就是剪枝一旦确定某一侧不平衡整个判断就地结束不需要继续浪费时间去算剩余的高度。我自己的理解是这种“返回值既要表达数据又要表达状态”的模式在处理很多树形给一个判定问题的时候都特别好用。比如判断对称、判断是否同一棵二叉树、判断子树结构都可以用类似的哨兵位写法。3. 实操过程与核心环节实现3.1 最小深度递归版与层序版先上递归版核心就是处理好空子树的情况。我这里用Python演示但逻辑在任何语言都一样。# Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # self.val val # self.left left # self.right right class Solution: def minDepth(self, root: Optional[TreeNode]) - int: if not root: return 0 left self.minDepth(root.left) right self.minDepth(root.right) # 关键判断左空右不空只能走右边 if root.left is None and root.right is not None: return 1 right # 左不空右空只能走左边 if root.left is not None and root.right is None: return 1 left # 两边都不空取较小值 return 1 min(left, right)很多人会把最后一行写成return min(left, right) 1就完事漏掉了中间两个单分支的判断。上面那个“只有右子树”的例子就是雷区。再补一个层序遍历版本遇到叶子直接返回当前层数from collections import deque class Solution: def minDepth(self, root: Optional[TreeNode]) - int: if not root: return 0 queue deque([root]) depth 1 while queue: size len(queue) for _ in range(size): node queue.popleft() # 找到第一个叶子即最小深度 if node.left is None and node.right is None: return depth if node.left: queue.append(node.left) if node.right: queue.append(node.right) depth 1 return depth我实际跑下来BFS版遇到矮树的时候比递归更快因为BFS只遍历到最近叶子所在层就停了递归会走完两侧所有分支。但如果树很深但比较均匀两者差距不会太大。3.2 节点计数两种实现对比通用遍历版class Solution: def countNodes(self, root: Optional[TreeNode]) - int: if not root: return 0 left_count self.countNodes(root.left) right_count self.countNodes(root.right) return 1 left_count right_count这就是一个后序统计没有难度适合做基准写法。优化版利用完全二叉树结构class Solution: def countNodes(self, root: Optional[TreeNode]) - int: if not root: return 0 left, right root.left, root.right left_height, right_height 0, 0 # 一路向左求左子树高度 while left: left left.left left_height 1 # 一路向右求右子树高度 while right: right right.right right_height 1 # 左右高度相等说明是满二叉树 if left_height right_height: return (1 (left_height 1)) - 1 # 否则向下递归 return 1 self.countNodes(root.left) self.countNodes(root.right)这里有一个容易忽略的点满二叉树公式是2^h - 1但h表示树有几层。如果root本身是第0层一直向左走到叶子一共走了left_height步那么总层数是left_height 1。所以直接(2 left_height) - 1也可以但写成(1 (left_height 1)) - 1更清晰。我之前犯过一个错把位运算写成1 left_height少了加1结果在这种短树上少算了节点调试半天才发现是层数算错了。这里提醒大家注意基准层的含意。3.3 平衡判断带剪枝的后序遍历class Solution: def isBalanced(self, root: Optional[TreeNode]) - bool: def check(root: Optional[TreeNode]) - int: if not root: return 0 left_height check(root.left) if left_height -1: return -1 right_height check(root.right) if right_height -1: return -1 if abs(left_height - right_height) 1: return -1 return max(left_height, right_height) 1 return check(root) ! -1这个写法有两个关键点。第一个是检查左子树后立刻判断是否为-1如果不检查就把返回值继续往上抛代码会陷入重复的“计算再发现是-1”的循环里。提前判断能够尽早返回效率更高。第二个是当前节点返回的是max(left_height, right_height) 1。因为左右子树高度差已经判断过不超过1了向上返回时只需要返回本层高度也就是较高子树的深度加1。我刚开始写的时候容易把返回值写成abs(left - right)其实那是差异值不是高度。记住这里向上传导的是“真实高度”判定结果是通过-1哨兵表达不是通过高度值本身表达。4. 常见问题与排查技巧实录4.1 为什么二叉树代码总是报运行时错误先回答热搜里最扎心的一个问题写二叉树程序时为什么总是报运行时错误。我的经验是90%的运行时错误都逃不出下面这三类。第一类是空指针解引用。最常见的就是没有判断root是否为空就访问root.val或者在递归里访问了node.left.left但node.left本身是空。这个错误在LeetCode上通常表现为AttributeError: NoneType object has no attribute val在C里就是Segmentation fault。第二类是递归忘写终止条件。或者是终止条件写得不对导致函数无限向下递归栈溢出。比如判断平衡树的时候只判断了root为空没判断递归子树中遇到的空节点导致访问空节点属性。第三类是递归参数传错引用。很多初学者喜欢把左右子树的高度计算结果写在参数里传递写成了“带状态的前序遍历”结果一层一层返回的时候值已经不对了。排查思路也很简单先检查所有出现.left、.right、.val的地方问自己一句“这个节点有没有可能是None”。把所有可能的None路径都写清终止条件问题基本就解决了一半。另一半在于给自己写的递归函数画一张返回路径图不要靠猜。4.2 深度、高度、节点计数的顺序混淆这三个概念在二叉树题目里是经常混用的。深度从根节点到当前节点的边长从上往下数。高度从当前节点到最远叶子的边长从下往上数。节点计数全树所有非空节点的数量。在递归实现里你通常需要先处理左右子树才能算当前节点的高度这就是后序。深度则更适合前序因为你在向下走的过程中一层层加1。节点计数两者都可以但后序更自然。很多人会把最大深度和高度搞混以为它们是两个算法。实际上最大深度就是从根出发算整棵树的高度也是从根出发算在数值上两者相等。真正容易出错的不是概念本身而是返回值的方向。我建议每写一道树题先在注释里写清楚# 当前递归要返回什么 # 1. 这棵子树的高度 # 2. 这棵子树的节点数 # 3. 是否满足某种条件布尔值或哨兵值搞清楚这个问题示例代码的结构就不会乱。4.3 边界情况自查清单二叉树的题很容易在边界情况上翻车我整理了一个自查清单以后做题可以直接套用。空树root为None返回值应该是0还是某个默认值。只有一个节点左右孩子都是None最小深度为1节点数为1平衡树。只有左子树或只有右子树的链状树最小深度不是1而是链的长度节点数就是链的长度平衡树如果链太长则不成立。完全二叉树最后一层不满的情况节点计数时左子树和右子树高度不相等会走递归分支。非常不平衡的树比如极端情况下退化成链表递归深度可能很大要注意栈溢出可以考虑迭代栈或BFS。这三个题里对单侧子树的关注尤其重要因为链状结构在最小深度里是最容易出错的场景。4.4 后续延伸方向与题目串联刷完这三道题可以顺势往下面几个方向延伸。搜索二叉树BST相关题目往往也用后序遍历的结构但会把返回值的语义从“高度”换成“区间范围”。比如判断一棵树是不是BST就不是单纯比较左右孩子而是要维护一个取值范围同时还要处理重复值的边界和平衡树的做法不一样。线索二叉树会让你重新理解遍历顺序。线索化其实就是把空指针利用起来指向中序前驱或后继这又回到了指针和遍历顺序的关系上。今天这三道题练熟了递归和指针操作再学线索二叉树就会有底气。另外节点计数这个题还可以联想“完全二叉树的最近公共祖先”之类的题目。那种题也是利用完全二叉树的路标特性从根节点一直到某个节点的路径可以用二进制表示出来和今天算高度的思路异曲同工。我的建议是不要急着去背更多新题目先把今天这三道的“返回值语义”自己讲一遍能不看代码把思路写出来再做两三个同类型题巩固一下。写在最后我个人实际刷下来的体会是今天最大的收获不是会做三道题而是彻底明白了“递归返回值是要表达意图的”。最小深度那道题如果你只是机械地改max为min会死得很难看。只有把“叶子节点”这个定义想清楚才能写出正确分支。这说明做题不能只背代码要搞清楚每个分支成立的场景。最后再分享一个小技巧遇到树的问题优先画图其次写层序遍历最后才碰递归。先把结构看清楚再动手写代码会顺手很多。特别是完全二叉树这种结构特性比较强的题画一遍图基本就能想到高度比较和位运算优化。你接下来如果刷到其他树形结构题目可以试试先画图再套这三道题的框架会轻松很多。
