二叉树这三个字大概是每个写代码的人都会撞上的一道坎。不管是准备校招、准备跳槽面试还是日常业务里处理菜单树、组织架构、表达式解析它总会以各种形式冒出来。我这些年刷过不少树的题目也带过几个新同事看他们被递归虐得欲哭无泪越来越觉得二叉树题目看似千变万化其实大部分嵌套在几个固定套路里。这篇《二叉树总结1》先把地基部分彻底讲透定义、遍历、基础操作、出问题后怎么排查适合刚学数据结构的人也适合想系统梳理一遍算法的老手。后面我计划继续更新这个系列把更复杂的题型逐步拆开。1. 先搞清楚二叉树的定义与核心特性1.1 为什么是“二叉”先看节点的结构二叉树的核心定义只有一条每个节点最多有两个子节点。这句话看起来简单但里面藏着一个容易被忽略的关键点——两个子节点是有顺序的分为左子节点和右子节点。也就是说即使两个节点的值一样一个作为左子树、一个作为右子树整棵树的结构仍然不同。很多人在写代码时忽略了“左右顺序”导致判断树是否对称、是否相同时踩坑。从代码上看最典型的节点结构就三样东西class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right rightval 存值left 指向左子树right 指向右子树。用 null或者 Python 里的 None表示“这里没有孩子”。正是这个“空”的概念让二叉树有了递归的基础一棵树要么是空的要么是一个根节点加上左右两棵子树。这个定义几乎就是递归函数的天然模板后面所有遍历、计算高度、判断平衡的代码本质上都是在套这个模板。可以拿链表做类比单链表是每个节点最多一个后继的线性结构而二叉树是每个节点最多两个后继的分叉结构。实际业务里部门组织架构、商品分类目录、前端组件树都是树的典型场景。二叉树则是最精简的“分叉模型”把多叉树的复杂度砍到只剩左右两支方便研究算法。1.2 满二叉树、完全二叉树、平衡二叉树区别与用途除了最基本的二叉树面试和实际开发里还会碰到几个特殊形态名字很容易记混这里一次性梳理清楚。满二叉树每个非叶子节点都有两个子节点且所有叶子都在同一层。换句话说每一层都是满的。严格意义上的满二叉树节点数遵循 2^(h1) - 1 的公式h 为高度。这种树很“完美”但实际数据里很少天然长成这样更多是题目构造出来的。完全二叉树除最后一层外每一层都填满且最后一层的节点从左到右连续排列中间不能有空缺。这个性质极其重要因为完全二叉树可以直接用数组存储不需要指针。堆优先队列就是建立在完全二叉树之上的典型数据结构下标 i 的节点左孩子是 2i1右孩子是 2i20-based 下标。能够用数组存树是堆排序和 Dijkstra 算法能高效实现的关键前提。平衡二叉树通常指左右子树高度差不超过 1 的树。这里的“平衡”是一个动态维护的概念比如 AVL 树、红黑树都是平衡树的工程实现。普通二叉搜索树在最坏情况下会退化成一条链表查找复杂度从 O(log n) 变成 O(n)引入平衡机制就是解决这个退化问题。面试中经常考“判断一棵树是否平衡”本质上就是在考递归返回信息的技巧后面会专门展开。这三个概念不需要死记定义重要的是理解它们各自解决什么场景的问题满二叉树和完全二叉树更多出现在理论推导和堆结构中平衡二叉树则是工程中保证查询性能的核心手段。2. 遍历是必考题递归写法与迭代写法一次讲清2.1 深度优先遍历前序、中序、后序的递归模板遍历是二叉树所有题目的基本功。所谓深度优先遍历就是沿着一条路径走到黑再回头走另一条。按访问根节点的时机分成前序、中序、后序三种顺序。前序遍历顺序是根 → 左 → 右。中序遍历左 → 根 → 右。后序遍历左 → 右 → 根。记忆方式可以看“根”出现在哪里根在前面就是前序根在中间就是中序根在最后就是后序。递归代码非常简洁下面这版直接返回遍历结果列表def preorder(root): if root is None: return [] return [root.val] preorder(root.left) preorder(root.right) def inorder(root): if root is None: return [] return inorder(root.left) [root.val] inorder(root.right) def postorder(root): if root is None: return [] return postorder(root.left) postorder(root.right) [root.val]很多初学者不理解为什么“打印节点”的位置变一下整个顺序就变了。我的理解方式很简单递归调用本质上是在模拟一个函数调用栈每次进入一个节点先处理什么、后处理什么取决于代码写在哪一次调用之前或之后。前序是“进入节点后立刻处理再进入左子树等左子树全部处理完回到这里再进入右子树”。中序是“先一头扎进左子树等左子树处理完回到当前节点处理当前节点再进右子树”。后序则是“左右子树都处理完最后才处理当前节点”。这三种顺序在应用上各有侧重。前序可以用于复制树的结构因为先处理根能最快建立新节点。中序在二叉搜索树中遍历出来是一个有序序列因为 BST 的性质就是左小右大。后序适合先处理完所有子节点再处理父节点的场景比如删除整棵树、计算子树规模。2.2 广度优先遍历层序队列模板与常见变式层序遍历也叫广度优先遍历是按层从上到下、从左到右访问节点。它天然就是用队列实现的因为队列先进先出正好符合“先入队的先访问”的层级关系。标准模板from collections import deque def level_order(root): if root is None: return [] res [] q deque([root]) while q: level [] for _ in range(len(q)): cur q.popleft() level.append(cur.val) if cur.left: q.append(cur.left) if cur.right: q.append(cur.right) res.append(level) return res这段代码里最有价值的是for _ in range(len(q))这一句。很多新手容易写成while q那样做会把所有节点一次性挤出来根本无法区分是哪一层的节点。原因在于pop 的同时也在 append 新节点队列长度一直在变化循环边界也就失控了。先固定当前层的长度再循环处理这样每一轮循环结束时队列里恰好是下一层的全部节点。层序遍历有很多看起来很花哨的变式本质上都是在这个模板上做小修改。比如“之字形打印”只需要加一个层号判断偶数层正序、奇数层反转即可。比如“二叉树右侧视图”就是取每层队列中最后一个节点的值。再比如“二叉树的最小深度”层序遍历遇到第一个叶子节点时直接返回当前层数这比递归解法更容易理解也不需要额外考虑递归深度问题。2.3 迭代写法当递归不再够用时怎么办面试中经常被追问“能不能不用递归实现遍历”另外当树退化成一条极深的链时递归可能直接导致栈溢出所以迭代写法必须会。前序遍历的迭代最简单。用一个栈先把根压入然后循环弹出节点处理再按照“先右后左”的顺序压入子节点。为什么要先右后左因为栈是后进先出想先处理左子树就得先把右子树压到栈底。def preorder_iter(root): res [] stack [root] if root else [] while stack: cur stack.pop() res.append(cur.val) if cur.right: stack.append(cur.right) if cur.left: stack.append(cur.left) return res中序迭代稍微难一点用双循环嵌套。一个指针 cur 从根开始一路把左孩子压栈直到左孩子为空时弹出栈顶节点处理再转向右子树。def inorder_iter(root): res [] stack [] cur root while stack or cur: while cur: stack.append(cur) cur cur.left cur stack.pop() res.append(cur.val) cur cur.right return res后序迭代可以取巧。前序是“根左右”如果把压栈顺序改成先左后右那么弹出顺序会变成“根右左”最后把结果整体反转就得到“左右根”的后序了。代码只需要在前序版本上稍微改动这个技巧在面试时特别好用。迭代写法本质上模拟的就是系统递归时的调用栈所以把它写一遍对递归的理解也会更深。我的建议是遍历代码不要只背一套递归和迭代都手写几遍直到不用想就能写出来。3. 经典操作的套路总结从高度计算到树的构造3.1 计算高度与节点数递归入门的第一个例子二叉树的高度、节点数是所有递归题里最简单的模板也是理解“分治思想”的起点。一棵树的高度等于左右子树高度的最大值再加 1空树高度为 0。这个逻辑一句话就能写出来def max_depth(root): if root is None: return 0 return max(max_depth(root.left), max_depth(root.right)) 1节点数同理整棵树的节点数等于左子树节点数加右子树节点数再加 1根节点本身def count_nodes(root): if root is None: return 0 return count_nodes(root.left) count_nodes(root.right) 1这两个例子虽然简单但它们是所有复杂递归的骨架。任何递归问题都可以拆成三个问题问自己空节点时我该返回什么当前这一层我要做什么操作左右子树递归回来的结果我要怎么合并只要把这三个问题想清楚递归函数基本就写对了。我见过很多人在复杂题上卡住回去一看其实是这三个基础问题没有形成直觉导致一遇到稍微变化的结构就慌。3.2 镜像、路径和、最近公共祖先高频题型的通用思路这几个题看起来差别很大实际上都是“递归函数返回什么信息”的不同版本。二叉树的镜像就是把每个节点的左右子树交换。可以用“后序式”的写法先递归镜像左右子树再交换根节点的左右指针def mirror(root): if root is None: return None left mirror(root.left) right mirror(root.right) root.left right root.right left return root这里为什么要先递归再交换因为只有先拿到两个孩子镜像后的结果才能把它们挂到正确的位置。如果先交换再递归逻辑上也能做但代码会别捏很多。面试官考这个题往往还会追问“判断一棵树是否镜像对称”思路是同时递归比较左子树的左孩子和右子树的右孩子本质上也依赖对递归返回结果的判断。路径和类题目比如“二叉树中的最大路径和”“路径总和”是另一大类热点。以最简单的“判断是否存在从根到叶子的路径和为 target”为例def has_path_sum(root, target_sum): if root is None: return False if root.left is None and root.right is None: return root.val target_sum return has_path_sum(root.left, target_sum - root.val) or has_path_sum(root.right, target_sum - root.val)核心思虑是把“总和等于 target”转换成“子树剩余需要满足的值”。每往下一层target_sum 就减去当前节点的值到叶子节点时只需判断当前值是否等于剩余目标。最近公共祖先题是递归返回值更加典型的一个代表。两个节点在一棵树里的最近公共祖先指的是离它们最近的共同父节点。递归写法非常经典def lowest_common_ancestor(root, p, q): if root is None 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直接返回否则分别去左右子树找。如果左子树找到了一个、右子树也找到了一个说明当前节点就是最近公共祖先如果只有一边找到了那一侧找到的节点就是答案说明两个目标节点都在同一侧。这类题的共性非常明显递归函数往往不直接返回最终答案而是返回“当前子树里找到的关键节点”再在父节点层合并左右结果。掌握了这个思路后面做树形 DP 类的题目会顺很多。3.3 二叉树的构造与序列化从遍历结果“反推”整棵树还有一种高频题型是根据遍历结果还原整棵树。最典型的是“从前序与中序遍历序列构造二叉树”。原理很简单前序遍历的第一个节点一定是根在中序遍历中定位到这个根根左边的部分属于左子树根右边的部分属于右子树再根据左子树、右子树分别有多少个节点把前序遍历的剩余部分切成两段递归构造左右子树。def build_tree(preorder, inorder): if not preorder: return None root_val preorder[0] root TreeNode(root_val) idx inorder.index(root_val) root.left build_tree(preorder[1:1 idx], inorder[:idx]) root.right build_tree(preorder[1 idx:], inorder[idx 1:]) return root这个写法好懂但实际面试时性能不够好。原因在于每次递归都调用index()在中序序列里查找根的位置时间复杂度是 O(n)再加上列表切片也会产生额外开销整体达到 O(n^2)。优化的做法是先用一个哈希表记录中序序列里每个值对应的下标把查找变成 O(1)配合下标区间而不是切片整体可以降到 O(n)。序列化与反序列化是构造类题目的延伸。序列化把二叉树变成一个字符串反序列化把这个字符串变回原来的树。常见的做法是用层序遍历普通节点先输出值再入队空节点输出 null 作为占位。反序列化时用一个队列逐个重建节点遇到 null 就不创建。这类题实战意义很强很多中间件存储树形结构时就是用类似的思路。4. 实操中的常见问题与排查技巧4.1 空指针异常最常见的翻车现场我几乎可以断言二叉树代码的报错里一半以上是空指针在 Python 里是 AttributeError本质差不多。最常见的场景是拿到了一个节点没做判空就直接访问node.val或者node.left结果在树的最深层翻车了。比如遍历完左子树后递归回到上一层此时如果某节点压根没有右子树代码里却不检查就访问立刻就会崩。这类问题的根源是“没有想清楚树里空节点的位置”。我自己的习惯是凡是处理 TreeNode 的代码第一步先问“如果这里是 None我该怎么办”。能提前想到空节点的处理逻辑很多报错可以避免。写递归时尤其要注意“退出条件里的空判断”不能省略。比如有的新手写if not root.left当作退出条件但真正的退出条件应该是if not root。这个差别不是小问题前者只在左孩子为空时退完全没考虑右孩子为空的情况。另外用 Python 写代码时还要区分node is None和node.val is None。树的节点值可能本身是空值不能用判断空节点的方式去判断节点值。4.2 递归层级过深栈溢出与效率问题Python 默认递归深度限制一般是一千层左右。当二叉树退化成一条链比如每个节点只有一个左孩子节点数几千个时递归解法就会直接报 RecursionError。Java 里面虽然默认栈空间大一些但过深的递归同样会导致 StackOverflowError。这种情况有三个处理方向。第一把递归写成迭代。比如前序、中序、后序遍历改成显式使用栈的方式完全绕开系统栈深度限制。第二配合尾递归优化思路调整代码结构但在 Python 中尾递归优化效果有限需要清楚这个限制。第三重新设计算法避免不必要的递归深度。比如判断平衡二叉树时如果设计成“在每个节点都递归计算左右子树高度再比较”一棵斜树的复杂度会退化得很严重。正确的做法是后序遍历在返回高度的过程中同时判断平衡一旦发现不平衡就提前返回 -1复杂度能从 O(n^2) 优化到 O(n)。这条经验在实际开发中很常见。处理真实业务里的树形数据时树深很容易超过一千层比如极度不平衡的组织架构或很深的评论楼中楼此时迭代或显式栈是更稳妥的做法。4.3 调试技巧自己写一个可视化打印函数二叉树一大痛点是很难直接看出结构。单步调试有时也会被绕晕尤其是递归嵌套深了以后调试器里的调用栈信息让人眼花缭乱。我后来专门写了个简单的打印函数用缩进来展示树的形状def print_tree(root, indent0): if root is None: return print( * indent str(root.val)) print_tree(root.left, indent 2) print_tree(root.right, indent 2)这个函数会把树打印成类似下面这样的效果5 3 2 4 8 7虽然打印方向是旋转了九十度的树但至少能一眼看出左右子树各自长什么样。调试递归时配合打印语句比盯着数据结构和内存地址高效太多。我测试树的特性时都会先跑一遍这个函数确认树构造对了再继续后面的逻辑。还有一个排查技巧适用性很广在递归函数入口处打印当前节点和当前状态然后观察调用顺序和预期是否一致。比如调试前序遍历如果你在打印当前节点值时函数入口也打印了一行“进入节点 xxx”等到递归返回时再打印“离开节点 xxx”就能非常直白地看到“递”和“归”的完整路径。这个方式虽然原始但对理解递归帮助极大。5. 学习路径与刷题建议5.1 三阶段学习法模板、理解、变形我梳理过不少新手的学习过程觉得二叉树的学习路径可以分成三个阶段。第一个阶段是“照猫画虎”。先把遍历、最大深度、节点个数、层序遍历这一批最基础的代码背下来达到能默写的程度。这个阶段不需要过度讲道理先把手感建立起来。就好比学骑车先骑上去再说。第二个阶段是“理解递归”。不再满足于背模板而是要能解释清楚每个递归函数里“空条件返回什么、递归调用返回什么、上一层怎么合并”。这个阶段的检验标准是随便拿一道树的题目你能在纸上画出递归的调用路径说清楚最深的叶子节点返回后上一层的状态是什么。第三个阶段是“灵活变形”。把二叉树当成处理树形数据的通用手段能自己设计递归返回结构。比如返回单个值不够用时考虑返回(is_balanced, height)这样的元组比如面对多叉树时能快速把二叉树递归改成循环遍历所有孩子。到这个阶段二叉树对你来说就不再是算法题而是一种解决问题的思维工具。5.2 题型分类与刷题顺序参考二叉树题目的数量很多但分类并不复杂。我建议按照下面的顺序刷能避免在题目海洋里迷失方向阶段题型核心目的基础前序、中序、后序、层序遍历建立递归和迭代的模板状态计算最大深度、节点数、平衡判断理解递归返回值路径类路径总和、最大路径和、二叉树的直径练习带条件的 DFS结构变换镜像、对称、翻转理解对树的重建过程祖先类最近公共祖先掌握合并左右子树结果构造类前序中序构造、序列化反序列化深入理解遍历结果与树的关系高级二叉搜索树系列、Morris 遍历拓展边界能力面试加分项每个阶段挑三到五道题认真吃透比盲目刷几十道题效果好。所谓“吃透”不只是能 AC而是能解释清楚每一步为什么要这么写。一个实用的学习小技巧每道题做完后把核心递归函数用中文注释重新写一遍把“空条件做什么、当前层做什么、递归回来合并什么”写清楚。这个习惯能强迫自己把模糊的理解变成清晰的逻辑等到面试时自然就能边说边写了。写这篇总结的时候我重新翻了一遍自己以前的笔记发现踩过的坑大多集中在“想当然”上——以为递归写对了其实退出条件漏了以为迭代稳了结果顺序正好弄反。根据我个人的经验二叉树的基础一定要亲手写到能默写的程度不要只在 IDE 里运行通过就完事面试时可没有自动补全也没人帮你调试。这个系列后面我准备继续写第二篇专门把树上递归与动态规划结合的题型整理出来比如打家劫舍三连、树形 DP 这类题目到时候再细聊。