刷算法题这些年我有一个特别深的感触二叉树这棵树太多人是靠背遍历模板混过来的。前序遍历、中序遍历、后序遍历背得滚瓜烂熟层序遍历也能默写但一旦遇到稍微需要自己设计的题目——比如判断平衡二叉树、求两个节点的最近公共祖先、计算二叉树直径——就彻底卡壳。这不是努力不够也不是智商问题而是没建立起属于二叉树这类题目的底层思考方式。我把它概括成四个字分解问题。极端一点说几乎所有二叉树问题都可以翻译成一句话——先求左子树能给我什么再求右子树能给我什么最后想清楚两侧信息怎么组合成当前这棵树的答案。这篇内容就是围绕这套分解问题的解题模式展开的。适合刚开始刷二叉树、或者刷了几十道但总觉得没有体系的读者。我会从原理讲到模板再用几道经典题演示完整落地最后专门聊一聊为什么你的二叉树程序总是报运行时错误这个几乎人人都踩过的坑。1. 先拆清楚二叉树为什么天然适合分解问题这条思路1.1 树本身的递归结构就是分解的出厂设置很多人没有意识到一件事二叉树定义本身就是递归的。一棵二叉树要么是空树要么由一个根节点加上左子树和右子树组成。而左子树和右子树各自又是一棵二叉树。这意味着什么意味着当你面对一个二叉树问题时你其实面对的是一个同构的、规模更小的问题集合。根节点处理完剩下的左子树和右子树是两棵独立的、结构完全一样的树。这种大问题里套着两个小问题、小问题又套着更小的问题的形态就是分解问题最理想的应用场景。对比一下链表。链表也有递归结构但它是线性的——一个问题最多只派生出一个子问题一路推进即可。而二叉树一次派生出两个子问题你不光要分别解决它们还得把两个结果揉到一起。这个揉到一起的环节恰恰就是大部分二叉树题目的考点所在。1.2 分解问题的两个层次结构分解与结果组合我习惯把分解问题拆成两层看结构分解当前的树拆成根节点、左子树、右子树三个部分处理根节点这层逻辑然后把左右子树交给同一套逻辑继续处理。结果组合左右子树各自返回一个答案你要设计一套规则让这两个答案再加上根节点自己的信息共同构成当前这棵树的答案。结构分解是标准的递归调用几乎所有题都一样结果组合才是每道题的灵魂。举两个例子你就有感觉了求二叉树的最大深度结果是左右子树深度的较大值加 1def maxDepth(root): if not root: return 0 left maxDepth(root.left) right maxDepth(root.right) return max(left, right) 1判断两个二叉树是否相同结果是左右子树是否相同且根节点值相等def isSameTree(p, q): if not p and not q: return True if not p or not q: return False return p.val q.val and isSameTree(p.left, q.left) and isSameTree(p.right, q.right)看到没结构分解完全一样但组合逻辑不同题目就不同。所以学二叉树与其背题解不如练组合逻辑设计的能力。1.3 自顶向下与自底向上信息流向决定代码形态分解问题还有两种信息流向这个理解透了很多题能一眼看出怎么解自顶向下先处理当前节点把某种状态传给子树。典型如路径总和——带着目标值一路减下去子树只要判断剩余值是否等于节点值。自底向上先让子树算完把结果汇总给当前节点。典型如最大深度、平衡二叉树判断当前节点的答案依赖左右子树的返回值。在实际题目里这两种方向往往可以互相转化。比如求二叉树某个节点的深度自顶向下带一个 depth 参数下去也可以自底向上让子树返回高度再加 1。没有绝对优劣只是在特定题里某一种更直观、更高效。这个到后面第 3 章的平衡二叉树例子中你会看到选错方向会带来灾难性的性能问题。2. 提炼一套可复用的分解模板递归设计的四个关键问题接触过递归的人都知道递归三板斧终止条件、递归调用、返回处理。但落到实际题目里很多人还是不知道递归函数里该写什么、返回什么。我给自己总结了一套设计模板写递归前先回答四个问题设计问题说明判断标准1. 这个函数在做什么函数的功能定义一句话说清楚定义不清晰后面一定写乱2. 返回什么才能回答题目是布尔值、数值还是节点引用或是组合结果返回值设计对了组合逻辑自然顺3. 空节点时返回什么终止条件的返回值必须符合组合逻辑很多坑都出在这一步4. 左右子树的返回值如何组合这是当前节点与子树之间唯一的信息通道组合逻辑代表你真正解题的部分下面用四道题性把它具象化这题是判断一棵树是否是平衡二叉树你会看到同样的模板怎么套进去。2.1 模板落地从最大深度到节点个数先看最简单的例子统计二叉树节点个数函数在做什么返回以 root 为根的树的节点总数返回什么整数空节点返回什么0空树没有节点组合逻辑左子树节点数加右子树节点数再加 1根节点自己def countNodes(root): if not root: return 0 return countNodes(root.left) countNodes(root.right) 1这个模式你看熟之后会发现节点个数、最大深度、最小深度、直径、路径总和全部是同一个骨架差异只在返回值和组合逻辑。2.2 再进一步带参数状态的分解有些题目光靠左右子树返回值还不够需要在向子树递归时携带上下文信息。这就是自顶向下的分解。比如求二叉树的最小深度根节点到最近叶子节点的距离def minDepth(root): if not root: return 0 if not root.left: return minDepth(root.right) 1 if not root.right: return minDepth(root.left) 1 return min(minDepth(root.left), minDepth(root.right)) 1这个题有个经典坑很多人直接写min(left, right) 1结果遇到根节点只有右孩子的情况会算出 1。因为空子树返回 0被当成深度 0参与比较了。实际上空子树不代表深度 0而是这条路不通。所以你看分解问题时空节点返回什么这个设计问题非常关键——你返回 0 是让上层把它当作没有贡献而某些场景里它需要表达的是此路不通。这就是四问模板第一问和第二问的意义返回值的设计本身就在承载语义。2.3 模板的边界与局限这个模板也不是万能的。碰到需要回溯收集路径的题目比如输出根到叶子的所有路径用纯粹的返回值分解就有点别扭因为路径信息是累积在过程中的不是由子树单方面返回的。这类题更适合回溯 全局变量或者携带路径列表下传的方式。我的经验是先判断题目要的是结果值还是要路径。要结果值用返回式分解要路径就要考虑回溯。别用一套模板硬套所有题否则会越套越痛苦。3. 五道经典题走一遍从读题到落盘的全过程这一节选五道覆盖不同组合逻辑的题我按实际做题的顺序把分解过程完整写出来包括我当时的思考路径而不是直接丢一个最终答案。3.1 二叉树的最大深度最直觉的分解也是入门的定海神针题目大家都熟求二叉树最大深度。分解点在于一棵树的最大深度是左子树最大深度和右子树最大深度中的较大者再加上根节点这一层。def maxDepth(root): if not root: return 0 return max(maxDepth(root.left), maxDepth(root.right)) 1这个解法的关键在空节点返回 0。有人问为什么不是返回 1想象一棵空树深度是多少应该是不存在深度定义成 0 恰好能让上层只加了根节点这一层。你多画几个例子就能接受这个设定。这个题的扩展特别多直径、最宽层、最近公共祖先的深度判断底层逻辑都跟这题有关。把这一题真正吃透比盲目刷十道新题都有用。3.2 平衡二叉树的判断分解方向选错性能天差地别判断一棵二叉树是否高度平衡——即每个节点的左右子树高度差不超过 1。我第一反应是自顶向下写先判断当前节点是否平衡再递归判断左右子树。于是写出了这样的代码def isBalanced(root): if not root: return True if abs(maxDepth(root.left) - maxDepth(root.right)) 1: return False return isBalanced(root.left) and isBalanced(root.right)这个写法在 LeetCode 上能过但性能极差。因为maxDepth在每次判断中都要完整遍历子树整棵树会面临大量重复计算。最坏情况严重偏斜的树下复杂度会退化成接近 O(n²)。正确的分解方向是自底向上——在求高度的同时顺便判断平衡性。让递归函数返回一个特殊值表达不平衡def isBalanced(root): def height(root): if not root: return 0 left height(root.left) right height(root.right) if left -1 or right -1 or abs(left - right) 1: return -1 return max(left, right) 1 return height(root) ! -1这个题给我的教训很深刻分解的方向自顶向下还是自底向上不只是风格问题直接决定算法复杂度。看到子树高度差这类和子树高度强相关的题目优先考虑自底向上在计算高度时顺手把平衡性检查做掉。3.3 路径总和把参数带下去的分解题目给一棵二叉树和一个目标值判断是否存在一条根到叶子的路径路径上节点值之和等于目标值。这个题是带参数分解的典型。每一层递归剩下的问题变成这个子树中是否存在一条从根到叶子的路径和等于 target 减去当前节点值。def hasPathSum(root, targetSum): if not root: return False if not root.left and not root.right: return root.val targetSum return hasPathSum(root.left, targetSum - root.val) or hasPathSum(root.right, targetSum - root.val)注意空节点返回 False因为空路径不能代表任何和。而叶子节点左右孩子都为空直接判断当前值是否等于剩余目标值。这个题的边界处理和最小深度一样容易翻车根本原因都是空节点在某些问题里不能当作值为 0的普通节点它代表不存在。3.4 对称二叉树跨左右子树的组合判断二叉树是否轴对称。这里有个思维跳跃单独一棵树的对称要转换成比较两棵树是否互为镜像。分解点变成了两个树节点之间的比较p 和 q 互为镜像当且仅当 p.val q.val、p.left 与 q.right 互为镜像、p.right 与 q.left 互为镜像。def isSymmetric(root): def mirror(p, q): if not p and not q: return True if not p or not q: return False return p.val q.val and mirror(p.left, q.right) and mirror(p.right, q.left) return mirror(root.left, root.right)这类题提醒我分解问题的子问题不一定是当前树的左右子树有时候是不同树的对应部分。很多二叉树变种题翻转树、合并两棵树、判断子树都是这个思路。3.5 最近公共祖先左右信息汇总出答案给一棵二叉树和两个节点 p、q找它们的最近公共祖先。这个题的分解比较妙。递归函数在每个节点要回答的问题变成以当前节点为根的子树中p 和 q 的最近公共祖先是什么但直接这么想很绕换个方式会简单很多——递归返回这个子树中是否找到了 p 或 q以及找到谁。我用一种更直接的写法def lowestCommonAncestor(root, p, q): if not root or root p or root q: return root left lowestCommonAncestor(root.left, p, q) right lowestCommonAncestor(root.right, p, q) if left and right: return root return left if left else right核心逻辑是在某个节点上如果在左右子树里分别找到了 p 和 q说明当前节点就是最近公共祖先。如果只在某一侧找到说明这一侧的返回值既是找到的节点也是可能的祖先。这个题我当初啃了很久直到把分解思路理清才明白它不再是一个单纯的返回布尔值/数值的问题而是返回一个节点引用并且返回值身兼两职。所以四问模板里的第二问返回什么在这个题里尤其重要——想清楚返回的是找到的那个节点代码就顺了。4. 为什么你的二叉树程序总是报运行时错误六个高频坑的完整排查笔记这部分专门回应写二叉树程序时为什么总是报运行时错误这个热门问题。我整理了自己和很多人反复踩的六个坑并把一个典型错误的完整排查过程写出来你可以直接照着这个思路去定位自己的问题。4.1 六十秒定位一个完整的报错排查链路假设你写了这样一段判断对称二叉树的代码def isSymmetric(root): if not root: return True # 没有判空直接访问 val return root.left.val root.right.val and isSymmetric(root.left) and isSymmetric(root.right)运行起来大概率报AttributeError: NoneType object has no attribute val。排查顺序应该是这样的看报错行定位到root.left.val这一行说明root.left是 None。构造最小复现用例造一棵只有根节点或者根节点只有一个孩子的树立刻复现。回到递归出口找问题根节点只有一个左孩子时root.right为 None但代码没有特殊处理就直接访问.val必然炸。修复把两个节点同时为空作为正常出口把一个为空作为失败出口就能覆盖这种情况。修复后def isSymmetric(root): def mirror(p, q): if not p and not q: return True if not p or not q: return False return p.val q.val and mirror(p.left, q.right) and mirror(p.right, q.left) return mirror(root.left, root.right)这个案子里根本原因不是语法错误而是递归设计时遗漏了一种边界情况一个子树存在、另一个子树为空。4.2 高频坑一不判空直接访问子节点这是最高频的运行时错误没有之一。二叉树递归里空指针几乎总是来自两种情况当前节点存在但左右孩子可能为空当前节点本身就为空却还访问它的字段。解决办法只有一个习惯在递归函数的第一句想清楚当前节点为空时要返回什么再往下写。不要先写正常逻辑再补判空顺序反了就会漏。4.3 高频坑二递归出口设计错误导致返回了错误的值有人写最大深度时在maxDepth里先判断if root is None: return -1然后left 1。结果是边界情况全偏了 1。这种错不会崩溃但答案会默默出错非常难查。我的建议是用几个极端用例验证出口。空树返回几只有一个节点的树返回几把这两个值固定下来再套公式。4.4 高频坑三递归无限循环递归的终止条件没覆盖到某些路径就会无限递归最终RecursionError: maximum recursion depth exceeded。常见触发场景是忘记考虑空节点导致空树在递归中一直调用自己的root.left和root.right永远到不了出口。排查方法在递归函数第一行打印当前节点值运行一次看输出是否在一棵越来越小的树上持续循环还是走到了 None 上回来。打印会立刻暴露问题。4.5 高频坑四树深度过大撞上递归栈上限这个问题在本地调试和 OJ 上都很坑。Python 默认递归深度大约 1000 层如果题目给了一棵特别深的偏斜树退化成链表那种即使是正确的递归代码也会直接栈溢出。处理策略分两种把递归改成显式栈的迭代写法或者在做竞赛题时确认题目数据范围如果深度可能上万就不要用递归。这个坑在面试时特别容易被人忽略因为通常小测试样例根本触发不了。一定要在写完递归后问自己一句这棵树最深会到多少层4.6 高频坑五递归返回值被覆盖或丢失有人会在递归过程中修改返回值的引用导致返回值在被上层组合时已经变了。比如在递归里用result列表做累加却忘记了在回溯时还原状态最终路径列表里混进了不该有的元素。这类问题区别于前几个它们不是崩溃型错误而是结果错误型错误。排查口诀是在递归返回处打断点检查每次返回的到底是什么有时候你以为是 A 类型实际却是 B 类型。4.7 高频坑六把遍历和递归返回值混在一起我见过很多人在求最大直径时写一个递归函数一边遍历、一边用非局部变量更新答案同时又想通过返回值表达某个子树的高度最后两边互相干扰。其实这种需求要拆成两层一层负责自底向上返回高度另一层在递归过程中顺便记录答案。不要试图用一个返回值同时表达高度和直径语义会打架。def diameterOfBinaryTree(root): ans 0 def depth(root): nonlocal ans if not root: return 0 left depth(root.left) right depth(root.right) ans max(ans, left right) return max(left, right) 1 depth(root) return ans这里depth的返回值只表达高度直径用外部变量ans收集。语义清晰后代码就不容易出错了。5. 用分解视角串起热度很高的几个二叉树考点熟悉了分解思路后再回头看你列的这几个热搜词——二叉树的遍历、二叉树的深度、搜索二叉树、线索二叉树——会发现它们其实都能用同一套视角串起来。5.1 三种遍历本质是分解时组合顺序不同前序、中序、后序递归框架完全一样def traverse(root): if not root: return # 前序位置先访问根 traverse(root.left) # 中序位置左子树回来再访问根 traverse(root.right) # 后序位置右子树也处理完再访问根用分解语言的讲法遍历就是访问根节点的动作放在不同时机执行。前序是先处理自己再交给子树后序是先让子树处理完再处理自己中序是夹在左右子树之间。这和自顶向下、自底向上的划分正好呼应。理解这个对应关系后很多题的做法你就能自己推出来。5.2 二叉树的深度一类题的度量筋二叉树的深度、高度、层数、直径、平衡因子本质上都在问同一件事子树之间的垂直关系。而衡量垂直关系的最小积木块就是子树返回一个整数。你掌握了最大深度那五行代码就等于掌握了这一类题的发动机。剩下的问题只是这个整数在返回前要不要加 1要不要在递归中记录额外的全局答案。5.3 搜索二叉树利用有序性分解问题会变得更简单搜索二叉树BST的有序性让分解问题的模式更丰富。以验证 BST为例如果只做常规的left root right判断往往会漏掉左子树里不能出现大于等于根节点的值这种跨层约束。正确思路是在递归时带一个区间把问题分解成当前节点的值是否落在区间内左子树是否落在更窄的区间内右子树是否落在另一个更窄的区间内。def isValidBST(root): def check(node, lower, upper): if not node: return True if node.val lower or node.val upper: return False return check(node.left, lower, node.val) and check(node.right, node.val, upper) return check(root, float(-inf), float(inf))到这里你会发现BST 问题里的分解不只是按左右子树分还按值域区间分。这是这类题区别于普通二叉树题的关键。5.4 线索二叉树把递归回溯的隐含步骤显式化线索二叉树是一种利用空指针记录前驱/后继的存储形态目的是把中序遍历变成纯粹的线性推进不用靠递归栈来回溯。第一次学容易觉得它和递归无关但你跳出来看它其实是对中序遍历递归时依赖栈回溯这个机制的显式改造递归中序遍历靠函数调用栈在返回时找到下一个节点线索二叉树把下一个节点直接存在指针里线程化后就像沿着一条链表走到底。用分解视角看节点就是结构分解的最小单元而线索就是把分解过程中隐含的下一步提前算好、存起来。这也能解释为什么线索二叉树特别适合频繁遍历、每次遍历都要破除递归栈开销的场景。6. 本地调试的小技巧给自己造一棵测试树最后分享一个我长期在用的调试方法很基础但特别实用。刷题时很多人都是用在线评测的用例慢慢试效率很低。我更推荐在本地把二叉树构建函数写出来直接构造极端用例。比如用 Python 从一个列表构造二叉树class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right def build_tree(values, index0): if index len(values) or values[index] is None: return None root TreeNode(values[index]) root.left build_tree(values, 2 * index 1) root.right build_tree(values, 2 * index 2) return root然后你可以随手构造根节点只有一个左孩子这种容易出错的用例tree build_tree([1, 2, None, 3]) print(isSymmetric(tree)) # False且不会挂我在实际排查那类NoneType报错时几乎全部是在本地用这种两三个节点的极端用例快速复现的。在线评测平台一个用例跑出来的报错信息有限本地构造同样结构但规模更小的树观察递归行为往往一眼就能看到问题。这个习惯帮我省了大量时间去猜错误。另一个小技巧是在递归函数入口加一行调试输出打印当前节点值这样整个递归路径会一目了然。代码确认无误后再删掉这行。对二叉树这种结构清晰的题打印往往比断点更好用。二叉树题从来不怕用到怕的是没有一套统一的思考切入点。分解问题就是那个切入点。我刷到几百道题之后回头看发现最常写的还是那几步——分左右、问出口、定返回值、合结果。把这套模式练到肌肉记忆再往里的各种变体题基本就是在这个骨架上换肉了。