1. 为什么要死磕二叉树先聊聊这东西到底有多重要如果你是准备面试、准备考研、或者刚转行学编程的人二叉树绝对是你绕不过去的一座山。我见过太多初学者在链表、数组里如鱼得水一到二叉树就懵圈递归看不懂、遍历记不住、遇到题目不知道从哪下手。说实话这很正常因为二叉树是很多人第一次接触到的“非线性数据结构”思维方式要从“一个个节点往后走”切换成“分叉、递归、层层深入”这个坎迈过去后面图、堆、并查集都会顺很多。那么二叉树到底是什么一句话说清楚每个节点最多有两个子节点左孩子和右孩子的树形结构。但就是这样一个看似简单的结构衍生出了海量的经典题目二叉树的遍历、二叉树的深度、搜索二叉树BST、平衡二叉树AVL、线索二叉树、由先序和中序确定树的结构……这些题目不仅是面试高频考点更是锻炼递归思维、分治思想的绝佳素材。这篇文章我会把这些入门必学的二叉树经典题给你系统地捋一遍。不是简单贴个代码就完事而是把每道题的思考过程、坑点、变种都讲明白保证你看完能形成自己的解题框架而不是死记硬背。注意本文所有示例代码用Python编写但思路完全可以用任何语言实现。我尽量把逻辑讲透代码只是表达工具。适合谁看刚开始刷LeetCode的初学者、准备数据结构期末考试的学生、以及那些“看得懂教程、自己做就废”的朋友。如果你已经能轻松写出二叉树的前中后序遍历那这篇文章对你的提升有限可以跳着看AVL树和线索二叉树部分。2. 二叉树的四种遍历方式 —— 一切题目的地基2.1 前序、中序、后序到底在干嘛先搞清楚一个最基础的概念二叉树的遍历顺序。所谓前序、中序、后序指的是根节点被访问的时机前序先序根 → 左 → 右中序左 → 根 → 右后序左 → 右 → 根我用一个特别土但特别好记的类比来解释。想象你手里拿着一张地图上面画了从入口到出口的一条路路边有很多岔路每条岔路尽头又是一个景点有的岔路还有分岔。你要把所有景点逛一遍。前序遍历就像“每到一个路口就先把当前这个景点拍了照然后钻左边的岔路逛完左边所有岔路再回来逛右边的”中序遍历就像“先钻左边的岔路逛到底回到当前路口拍个照再钻右边岔路”后序遍历就像“先把左右岔路全逛完最后回到当前路口拍照”。这个类比帮你建立“访问时机”的概念真正写代码的时候你会发现三种遍历的代码长得几乎一模一样就是三行代码换顺序。class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right # 前序遍历根左右 def preorder(root): if not root: return [] return [root.val] preorder(root.left) preorder(root.right) # 中序遍历左根右 def inorder(root): if not root: return [] return inorder(root.left) [root.val] inorder(root.right) # 后序遍历左右根 def postorder(root): if not root: return [] return postorder(root.left) postorder(root.right) [root.val]你没看错就是递归的返回顺序换一下而已。我不建议刚入门就把迭代写法背得滚瓜烂熟——理解递归在先迭代是后面优化要考虑的事。2.2 层序遍历 —— 按行扫描的BFS除了前中后序这种“深度优先”的遍历还有一种是层序遍历也叫广度优先遍历。层序遍历就是从上到下、从左到右一层一层地扫。它的核心工具是队列。from collections import deque def level_order(root): if not root: return [] result [] queue deque([root]) while queue: level_size len(queue) level_nodes [] for _ in range(level_size): node queue.popleft() level_nodes.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(level_nodes) return result层序的变种题很多比如“之字形遍历”蛇形遍历、“右侧视角”这类题都是在层序遍历的基础上加一点料。层序遍历本身必须先吃透它同时也是后面求二叉树宽度、判断完全二叉树的基础。2.3 一个细节递归写法里的隐形坑这里我要说一个我当年踩过好几次的坑。很多新手会写成这样def preorder(root): result [] if not root: return result result.append(root.val) preorder(root.left) preorder(root.right) return result这段代码看起来没毛病跑起来结果却是[根节点的值]左子树右子树全丢了。原因很简单递归调用的返回值根本没接住append的结果在子调用里自生自灭。所以要么像我上面那样写成返回拼接列表要么用一个全局的result变量在递归中不断append。你实践的时候如果发现返回值不对第一反应就应该检查是不是这个原因。3. 知道先序和中序怎么确定一棵树—— 经典中的经典3.1 重建二叉树的原理这道题是无数面试官的心头好也是LeetCode第105题。题目给两个数组前序遍历结果和中序遍历结果要求重建出整棵二叉树。“知道二叉树先序和中序确定树的样子”这个热搜词点名的就是这道题。先说原理理解了原理代码就是水到渠成的事先序的第一个元素一定是根节点在中序里找到根节点的位置左边的全是左子树右边的全是右子树根据中序里左右子树的长度可以顺手把先序数组分成左子树部分和右子树部分。举个例子。先序是[3, 9, 20, 15, 7]中序是[9, 3, 15, 20, 7]。先序第一个元素是3说明根节点是3。在中序里一查3在第二个位置左边是[9]右边是[15, 20, 7]。好左子树有1个节点右子树有3个节点。再看先序去掉3之后是[9, 20, 15, 7]前1个是左子树的部分即[9]后3个是右子树部分即[20, 15, 7]。于是原问题拆成两个子问题用先序[9]和中序[9]重建左子树用先序[20, 15, 7]和中序[15, 20, 7]重建右子树。这就是典型的递归分治。3.2 代码实现def build_tree(preorder, inorder): if not preorder or not inorder: return None root_val preorder[0] root TreeNode(root_val) # 找到根节点在中序中的位置 root_idx inorder.index(root_val) # 中序中左子树的区间 inorder_left inorder[:root_idx] inorder_right inorder[root_idx 1:] # 先序中左子树有len(inorder_left)个节点 preorder_left preorder[1:1 len(inorder_left)] preorder_right preorder[1 len(inorder_left):] root.left build_tree(preorder_left, inorder_left) root.right build_tree(preorder_right, inorder_right) return root这版代码是“切片版”好理解但每次递归都创建新数组空间复杂度不理想。优化版本是用双指针下标记录子数组边界不切片直接在原数组上操作。3.3 延伸中序后序、先序后序同样的思路可以套到“中序后序”重建二叉树LeetCode第106题。后序的最后一个元素是根节点然后依然用中序去切分左右子树。但“先序后序”不能唯一确定一棵二叉树。为什么因为先序和后序都只能体现根的位置关系无法区分某一个节点到底是左孩子还是右孩子。举个例子根A只有一个左孩子B和只有一个右孩子B这两种情况下先序都是[A, B]后序都是[B, A]。所以先序后序能确定树的结构但无法确认它是左子树还是右子树。这个考点经常出现在选择题里属于概念辨析要留意。特别注意给先序中序重建二叉树的题目还有一个变种——不是返回TreeNode而是让你判断这棵树是否合法。核心还是先定位根再递归验证思路完全一样。4. 二叉树的深度问题 —— 从最大深度到最小深度再到平衡判断4.1 最大深度怎么求求二叉树的深度是另一道入门必做题。深度就是根节点到最远叶子节点的节点数有的定义是边数LeetCode默认是节点数。递归思路非常直接一棵树的最大深度 max(左子树最大深度, 右子树最大深度) 1。当前节点的这一层要算上所以加1。def max_depth(root): if not root: return 0 left_depth max_depth(root.left) right_depth max_depth(root.right) return max(left_depth, right_depth) 1就这几行。但这里面其实藏着一个很重要的思维模式你要相信递归函数已经帮你处理好了子问题你只需要关心当前层怎么把子问题的结果拼起来。初学者最大的障碍就是总想跟着递归一层层走到底把自己绕晕。正确做法是假设max_depth(root.left)已经返回了左子树的高度你只需要拿它和右子树比较然后加1。4.2 最小深度 —— 一个容易翻车的题最小深度的定义是根节点到最近叶子节点的节点数。注意“叶子节点”三个字这是最大的坑。很多新手直接写def min_depth(root): if not root: return 0 return min(min_depth(root.left), min_depth(root.right)) 1这代码在一种情况下是错的当一棵树只有一个左孩子、没有右孩子时比如root.left是一个叶子节点root.right是None。按上面代码右子树高度返回0min(左子树高度, 0) 1就直接等于1了。但根节点到最近的叶子节点明明是2根→左孩子。为什么会错因为None不是叶子节点空树也没有叶子节点。你拿0去和真正的叶子高度比较会把“不存在”当成“路径最短”。正确的写法是加一个判断def min_depth(root): if not root: return 0 # 如果左子树为空只能走右子树 if not root.left: return min_depth(root.right) 1 # 如果右子树为空只能走左子树 if not root.right: return min_depth(root.left) 1 # 两边都不为空取较小值 return min(min_depth(root.left), min_depth(root.right)) 1这个坑在面试里非常经典一定要记住最小深度不能无脑取min先处理一边为空的情况。4.3 平衡二叉树判断的核心思想平衡二叉树的定义任意一个节点的左右子树高度差不超过1。判断时直观想法是每个节点都去算左子树高度和右子树高度然后比较。但这会重复计算子树高度效率很低。更优雅的写法是用一个返回值同时传递两个信息当前子树是否平衡、当前子树的高度。Python里可以用-1代表“不平衡”高度值代表“平衡且高度为h”。def is_balanced(root): def check(node): if not node: return 0 left check(node.left) if left -1: return -1 right check(node.right) if right -1: return -1 if abs(left - right) 1: return -1 return max(left, right) 1 return check(root) ! -1这个解法的精妙之处在于只要发现某棵子树不平衡就直接返回-1不再继续递归相当于一套人马同时完成“判断”和“算高度”两件事时间复杂度从O(n²)降到O(n)。我在面试里常把这个当加分项讲给候选人听能把这层想明白的人递归功底基本没问题。5. 搜索二叉树BST与AVL树的入门玩法5.1 BST的特性为什么这么重要搜索二叉树Binary Search TreeBST是一种特殊的二叉树对于任意节点左子树所有节点的值都小于它右子树所有节点的值都大于它。这个性质带来一个极其重要的推论中序遍历BST得到的是一个升序序列。就这一条性质衍生出了一堆题。比如“验证一棵树是不是BST”方法就是中序遍历后检查是不是严格递增的。你甚至可以不用中序直接递归地给每个节点传一个取值范围区间(lower, upper)检查节点值是否在区间内——这其实更贴近BST定义的递归本质。def is_valid_bst(root): def validate(node, low, high): if not node: return True if node.val low or node.val high: return False return validate(node.left, low, node.val) and validate(node.right, node.val, high) return validate(root, float(-inf), float(inf))这里的细节是左子树的所有节点不仅要小于父节点还要大于父节点的父节点也就是界限low右子树同理。所以每个节点都带着一个“允许的取值范围”往下传左右子树分别收紧上界和下界。二叉搜索树的经典操作题还包括插入、删除、查找第K小节点等。插入和查找比较简单删除则要考虑三种情况叶子节点直接删只有一个孩子就让孩子顶上来有两个孩子就得找右子树中最小的节点后继来顶替。这个“后继替换”的思路是面试官非常爱问的点建议自己动手画几棵树推演一遍。还有一个容易混淆的概念搜索二叉树和堆的区别。堆只保证父节点大于或小于子节点但兄弟之间没有大小关系BST则保证全部的左子树节点小于根、全部的右子树节点大于根。这两个结构千万别搞混面试时概念说错会扣分。5.2 AVL树在入门阶段该掌握到什么程度AVL树是自平衡的二叉搜索树。它要求任意节点的左右子树高度差不超过1就是前面讲的平衡二叉树判断标准一旦失衡就要通过旋转来恢复平衡。入门阶段不需要手写完整的AVL树插入删除代码但你必须理解四种旋转LL型在左孩子的左子树插入节点导致失衡需要右旋RR型在右孩子的右子树插入节点导致失衡需要左旋LR型左孩子右子树插入导致失衡先左旋再右旋RL型右孩子左子树插入导致失衡先右旋再左旋。记忆窍门是哪个方向“重”了就往反方向旋。LL说的是“左-左”太重那就把根节点向右旋转把左孩子提上来当新根。LR是“左-右”先处理下半段的右旋让左孩子下面的结构变成一条直线再处理上半段的左旋。嵌入式的朋友对这个可能更敏感因为嵌入式系统经常要维护大量有序数据内存又有限AVL树相比红黑树实现简单、查找稳定在很多资源受限场景反而更实用。如果你在做嵌入式开发建议至少能把AVL树的插入旋转完整手写一遍。我自己当年学AVL树的时候死活记不住LR型为什么要转两次。后来用了一个笨办法每次都把那三个节点画出来看它们最终的排列顺序是“左中右”还是“中左右”再对照四种类型画了十几遍以后肌肉记忆就形成了。这个方法听起来笨但特别有效。6. 线索二叉树 —— 一个容易被忽略但很巧妙的设计6.1 线索二叉树解决了什么问题线索二叉树Threaded Binary Tree不是一个算法题而是一种存储优化思路。普通二叉树用链式存储时每个节点有两个指针但很多节点的孩子指针是空的。你可以数一下一棵有n个节点的二叉树总共有2n个指针其中只有n-1个指向了实际的孩子节点每个非根节点都有一条边指向它也就是有n1个空指针。线索二叉树的核心想法就是把这些空指针利用起来指向前驱或后继节点。具体做法是中序遍历时如果某个节点没有左孩子就把左指针指向它的中序前驱没有右孩子就把右指针指向它的中序后继。为了区分指针到底是指向孩子还是线索每个节点需要额外两个布尔标记ltag和rtag。线索二叉树的价值在于它让中序遍历不需要借助栈或递归就能线性地完成时间复杂度仍然是O(n)但空间上省掉了递归栈。对于需要频繁进行中序遍历的场景比如实现某些数据库索引的扫描很有意义。6.2 增加ltag和rtag后的节点结构class ThreadedNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left # 左孩子或前驱线索 self.right right # 右孩子或后继线索 self.ltag 0 # 0表示左指针指向左孩子1表示指向前驱 self.rtag 0 # 0表示右指针指向右孩子1表示指向后继线索化过程的核心是在中序遍历中记录前一个访问的节点然后把当前节点左空指针指向前驱前一个节点的右空指针指向当前节点。很多教材会把线索二叉树当作考试重点但实际工程中直接用它的场景其实不算多。我的建议是理解思路、能画图、能看懂代码如下足了不必花太多时间死磕如何构建线索二叉树因为面试和实践中它的出现频率远低于AVL树和BST。7. 二叉树另一个常考点二叉搜索树的最近公共祖先7.1 用BST特性快速解题这道题可以算是BST的“得意门生”题也是搜索二叉树的常客。LeetCode第235题是二叉搜索树的最近公共祖先LCA。如果给你的是普通二叉树LCA得从底向上找用后序遍历加递归比较麻烦。但如果是BST利用大小关系可以做到非常优雅。最近公共祖先的定义是在树中找到一个节点它同时是p和q的祖先并且离p和q最近。在BST里从根开始往下走会遇到三种情况当前节点值比p和q都大说明p和q都在左子树往左走当前节点值比p和q都小说明p和q都在右子树往右走当前节点值在p和q之间或者等于p或q当前节点就是分岔点也就是最近公共祖先。def lowest_common_ancestor_bst(root, p, q): while root: if root.val p.val and root.val q.val: root root.left elif root.val p.val and root.val q.val: root root.right else: return root return None这个方式不用递归一个循环就完事每次迭代都砍掉一半子树和二分查找一个思路。为什么当前节点的值在p和q之间时它就是最近公共祖先因为再往下走无论是左子树还是右子树都不可能同时包含p和q了——p和q已经分居在左右两侧。7.2 如果是普通二叉树呢如果题目不给BST只给一棵普通二叉树那就得换思路。常见递归解法是从底向上如果左右子树分别含有p和q则当前节点就是LCA如果只有一边含有则继续往上传递。def lowest_common_ancestor(root, p, q): if not root or root p or root q: return root left lowest_common_ancestor(root.left, p, q) right lowest_common_ancestor(root.right, p, q) if left and right: return root return left if left else right这个递归解法的精髓在于返回值的三层含义空表示当前子树不包含p或q等于p或q表示找到了目标等于其他节点表示这个节点是某个子树内的LCA。面试中把这三层含义说清楚比背代码重要得多。个人建议这两道LCA题非常建议放在一起刷对比着看。BST版本利用有序性把复杂度降到O(h)普通树版本是标准的自底向上递归。放在一起你能深刻体会到“数据结构特性”对算法设计的影响。8. 常见问题与排查技巧 —— 二叉树题目“突然不会了”怎么办8.1 递归返回值丢失前文已经提到最常见的问题就是递归调用后没有接收返回值。检查思路先看一眼递归函数的return语句是不是在每一层都被正确处理。我自己的习惯是先在纸上写出“当前层该返回什么”递归层之间的数据流理清了再动笔写代码。8.2 空指针判断遗漏二叉树题里root.left和root.right常常是None代码里漏判会导致AttributeError或者NullPointerException。一个经验是在进入递归或循环时第一行就处理空节点的情况。即使当前没有遇到空指针问题也建议在每个递归函数开头先写空判断这是预防性编程。8.3 递归层数过深导致栈溢出Python默认递归深度大概在1000左右。如果你的树是一条链比如只有左孩子的退化成链表递归深度就会等于节点数很容易爆栈。这时候有两个选择改成显式栈的迭代写法或者用系统设置增大递归上限。但面试时更推荐迭代写法因为说明你理解了手动模拟递归的过程。下面给一个迭代版前序遍历的模板其他遍历可以依葫芦画瓢def preorder_iterative(root): if not root: return [] result [] stack [root] while stack: node stack.pop() result.append(node.val) # 栈是后进先出先压右再压左保证左先出 if node.right: stack.append(node.right) if node.left: stack.append(node.left) return result8.4 画图是最后一道保险遇到二叉树题卡住了任何高深的技巧都不如动手画图。把测试用例画出来标注出每一步的递归调用和返回值。这个方法看起来慢但确实是我带过的人中公认最有效的排障方式。我见过很多新手在脑子里空想象了半天不如画三分钟图来得快。8.5 一个通用解题心法最后送大家一个心法二叉树题百分之八十可以归为“递归三步曲”。第一步明确递归函数的输入输出是什么第二步找到递归的终止条件通常就是空节点第三步确定当前层要做什么以及怎么把子问题的结果组合起来。做题之前先把这三步在脑子里过一遍很多题你甚至不用写代码就能想出解法。9. 几个建议 —— 怎么刷二叉树题才高效我个人带过不少新手也走过不少弯路总结几条实在的建议。第一先集中刷遍历。前序、中序、后序、层序每道题用递归和迭代各写一遍。四者之间代码差异很小但你写熟练之后很多衍生题就像搭积木一样简单。第二把“求深度”“求直径”“判断平衡”“判断对称”这种基础题放在同一批次练习。它们基本都是后序遍历的变种本质上是把每个节点的状态算出来并向上传递。集中刷的好处是你很快会发现模式而不是每道题都要重新想思路。第三不要死磕难题。作为入门碰到困难的二叉搜索树题目或者复杂的旋转先跳过保证基础题熟能生巧后再回来。第四自己给自己讲题。做完一道题把思路和实现讲给一个“虚拟听众”听。能讲明白才说明你真的懂了。这个技巧对面试准备尤其有用。我在实际刷题过程中最深的体会是二叉树题目其实是一座“思维健身房”。它不像动态规划那么抽象也不像图算法那么依赖复杂的模版它非常适合用来打磨一个人的递归直觉和分治思维。如果你能把二叉树的经典题刷得滚瓜烂熟再去接触红黑树、B树、哈夫曼树、线段树这些高级结构会发现底层逻辑都是相通的。最后再分享一个小技巧很多二叉树题目的测试样例你都可以自己手动构造一棵树然后打印遍历结果来验证思路。用Python的话我习惯写一个print_tree辅助函数把树的结构和节点值打印出来调试效率提升明显。二叉树这条路走通一次后面就是一马平川。希望这篇总结对正在爬这座山的你有帮助。