刷LeetCode Hot 100的朋友都知道前三十几题是数组、链表、哈希这些“开胃菜”做到第36题“二叉树的最大深度”时才真正开始进入树的世界。这道题在Hot 100里排序第36对应的原题是LeetCode 104。题面很短短到一眼就能看完给定一棵二叉树返回它的最大深度。但就这么一道看起来“送分”的题我见过太多人在笔试和面试里栽跟头核心问题不是不会做而是对递归理解不透、对边界条件考虑不全一到写代码就报运行时错误。这篇文章我打算从题目拆解开始把递归、迭代两种主流解法都过一遍再重点聊聊“为什么写二叉树程序总是报运行时错误”这个高频问题最后把二叉树深度这个概念延伸到遍历、搜索二叉树、线索二叉树等知识体系上。不管你是刚开始刷题的初学者还是准备面试想查漏补缺的选手这篇都值得你花十分钟认真读一遍。1. 题目拆解最大深度到底在问什么1.1 一句话读懂题目二叉树的最大深度指的是从根节点到最远叶子节点的最长路径上的节点数。注意是“节点数”不是“边的条数”。比如一棵只有一个根节点的树深度是1而不是0一棵空树深度是0。很多人在这个细节上出错一上来就把根节点算成0导致整个递归逻辑全偏了。LeetCode对这道题的定义也很明确给定二叉树 root返回其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。叶子节点是指没有子节点的节点。拿一个最简单的例子来说3 / \ 9 20 / \ 15 7这棵树的最大深度是3路径是 3 - 20 - 15或 3 - 20 - 7。注意左侧的 9 虽然存在但它的路径长度只有 2所以最大深度取的是右子树的深度加 1。1.2 为什么第一反应应该是递归树这种数据结构天然适合递归。因为每一棵子树本身就是一棵完整的二叉树根节点的左孩子是左子树的根右孩子是右子树的根。所以“求一棵树的最大深度”可以拆成“求左子树的最大深度”和“求右子树的最大深度”然后取较大值再加 1。这个思路不是靠硬背的而是树的递归定义决定的。你可以把“求根节点的深度”看成“求左子树深度”“求右子树深度”两个子问题而每个子问题又继续往下拆直到遇到空节点为止。这就是分治思想在二叉树上的直接体现。递归之所以是这道题的最优解还在于它的代码极其简洁逻辑和数学归纳法完全对应。数学归纳法有三板斧基础情况、归纳假设、归纳步骤。递归也对应有三板斧终止条件、递归调用、返回结果。只要这三样写对了代码基本不可能错。1.3 复杂度与边界条件先给结论递归解法的时间复杂度是 O(n)n 是二叉树节点总数。因为每个节点都会被访问一次做一次比较和一次加法。空间复杂度是 O(height)height 是树的高度。递归调用栈的深度等于当前递归层数而递归最深会沿着树的一条链一直走所以最坏情况下空间复杂度是 O(n)也就是树退化成链表的时候。边界条件有三个必须想清楚空树root 为 nullptr深度返回 0。只有一个根节点左右子树都为空深度返回 1。只有左子树或只有右子树不能只递归一边必须两边都递归因为可能是另一边的深度更深。第 3 点尤其容易错。很多新手会写if (!root-left) return maxDepth(root-right) 1;这种提前剪枝的逻辑看起来像优化实际上是画蛇添足。你只需要把左右子树的深度都算出来取 max根本不需要特判单边子树的情况。提前特判不仅代码啰嗦还容易漏掉一些隐藏逻辑。2. 三种主流解法与代码实现2.1 递归DFS一个变量走遍全树先给出最经典、也是面试中最推荐写的递归版本。/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int maxDepth(TreeNode* root) { // 终止条件空节点深度为0 if (root nullptr) { return 0; } // 递归计算左右子树深度 int leftDepth maxDepth(root-left); int rightDepth maxDepth(root-right); // 当前节点深度 子树最大深度 1 return max(leftDepth, rightDepth) 1; } };这段代码一共不到十行但每一行都有讲究。第一if (root nullptr) return 0;是终止条件少了这一行递归就会无限循环往下访问空指针的 left 和 right直接报运行时错误。第二int leftDepth maxDepth(root-left);和int rightDepth maxDepth(root-right);是递归调用。注意这里不能写成return max(maxDepth(root-left), maxDepth(root-right)) 1;吗当然可以功能完全一样。但我个人建议新手先用中间变量接住返回值方便调试时看每一层的结果。第三返回值是max(leftDepth, rightDepth) 1。这个1代表当前节点本身。你在纸上画一棵三层二叉树从空节点一路回溯会发现每往回走一层就加一次 1最后根节点的深度正好是整棵树的高度。递归版本的执行过程可以用“递”和“归”两个字来理解。“递”是从根节点一路往下走直到空节点“归”是从空节点一层层往回返每层返回一个深度值。这个过程中左右子树的深度互不干扰最后在根节点处汇合、比较、取最大。2.2 迭代BFS层序遍历数层数递归虽然简洁但有些面试官会追问“不用递归怎么做”或者要求你写出迭代版本。这时候 BFS广度优先搜索/层序遍历是最直接的思路。层序遍历天然和“深度”绑定你一层一层往下扫扫了多少层深度就是多少。class Solution { public: int maxDepth(TreeNode* root) { if (root nullptr) { return 0; } queueTreeNode* q; q.push(root); int depth 0; while (!q.empty()) { int levelSize q.size(); // 当前层节点数 for (int i 0; i levelSize; i) { TreeNode* node q.front(); q.pop(); if (node-left) q.push(node-left); if (node-right) q.push(node-right); } depth; } return depth; } };这里有一个非常关键的细节int levelSize q.size();必须在for循环之前取。如果写成for (int i 0; i q.size(); i)由于循环体内会不断 push 新节点q.size()会一直变化导致当前层节点的边界完全错乱。这是层序遍历最常见的一个 BUG。为什么 BFS 能数出深度因为while每循环一次队列里刚好存放当前层的全部节点。处理完这一层后队列里剩下的是下一层的全部节点。depth每次循环都会执行所以循环次数就是层数即深度。BFS 的时间复杂度同样是 O(n)空间复杂度在最坏情况下是 O(n)。什么是最坏情况二叉树的最后一行节点数量最多那一行全部塞进队列时队列长度达到峰值。对于一棵满二叉树最后一层大约有 n/2 个节点所以空间复杂度是 O(n)。2.3 迭代DFS用栈模拟系统栈除了 BFS还可以用迭代的方式模拟递归的 DFS。思路是手动维护一个栈栈里保存“节点”和“当前节点深度”的配对信息。每弹出一个节点就用它的深度更新最大值然后把左右孩子连同它们的深度压入栈中。class Solution { public: int maxDepth(TreeNode* root) { if (root nullptr) { return 0; } stackpairTreeNode*, int stk; stk.push({root, 1}); int ans 0; while (!stk.empty()) { pairTreeNode*, int cur stk.top(); stk.pop(); TreeNode* node cur.first; int depth cur.second; ans max(ans, depth); if (node-left) stk.push({node-left, depth 1}); if (node-right) stk.push({node-right, depth 1}); } return ans; } };这里用pairTreeNode*, int把节点和它所在的深度绑定在一起每次弹栈时都能准确知道当前节点在第几层。这里有个经验如果你在迭代遍历二叉树时需要记录路径信息、深度信息优先考虑用pair或者额外开一个平行栈千万不要试图修改 TreeNode 结构体加字段。LeetCode 的 TreeNode 定义是固定的你改了结构体本地能编译提交上去直接编译失败。迭代 DFS 的空间复杂度也是 O(n)最坏情况同样是树退化成链表时栈里会积累一整条链的节点。3. 运行时错误排查二叉树代码为什么总崩3.1 运行时错误的四大来源如果你搜过“写二叉树程序时为什么总是报运行时错误”应该能发现这个问题在初学者中极其普遍。根据我刷题踩坑和帮别人 debug 的经验运行时错误集中在以下四个来源空指针访问对 nullptr 调用-left或-right这是最常见的一类几乎占了 80%。递归死循环缺少递归终止条件或者终止条件写错导致栈溢出Stack Overflow。栈溢出递归深度过大超出系统栈容量。循环/递归边界错误比如 BFS 里q.size()动态变化、DFS 里访问了未初始化的指针。这四个来源里空指针访问和栈溢出又是重中之重。下面我各展开聊聊。3.2 空指针和空树90%崩溃的根源看一段典型的错误代码int maxDepth(TreeNode* root) { return max(maxDepth(root-left), maxDepth(root-right)) 1; }这段代码放在 LeetCode 上跑立刻报运行时错误。为什么因为当递归到达叶子节点的左右孩子时root已经变成了nullptr但代码还在调用root-left相当于对一个空指针取成员程序直接崩溃。这就好比你手上没有快递却非要看快递单上的收件人地址那肯定报错。正确的做法是先在函数入口判断root是否为空为空直接返回 0。把空节点当成深度 0既是递归的终止条件也符合题目定义。另外一个容易忽略的场景是输入本身就是空树。root nullptr函数直接走终止条件返回 0。如果你在调用maxDepth之前不检查 root 就访问root-val或root-left同样会崩。所以 LeetCode 的题目函数里凡是能接收指针的第一步先想这个指针能不能是空的。3.3 递归深度与栈溢出栈溢出是另一个高频运行时错误。LeetCode 默认给每个线程分配的栈空间有限通常只有 8MB 左右。每一层递归调用需要保存当前函数栈帧栈帧里含有参数、局部变量、返回地址等信息大约几十到几百字节。当二叉树特别深时递归调用链也特别深栈空间消耗殆尽就会报栈溢出。什么情况下树会特别深两种典型情况。第一种是树的形态很极端比如每个节点都只有右孩子一棵 n 个节点的树高度就是 n这棵树看起来更像一条链表。第二种是输入的节点数量非常大比如一棵满二叉树有 10 万层递归深度同样会爆炸。遇到这种问题有两个解决思路。把递归改成迭代 BFS 或迭代 DFS用堆上的 queue/stack 代替系统调用栈。如果题目允许研究是否有不需要遍历整棵树的数学解法。不过对“最大深度”这道题而言不存在这种捷径因为你总得看完所有节点才能确定最大深度。在实际面试中面试官一般不会故意给你一棵十万层的树来卡你。但你需要能说出“递归的瓶颈在栈空间极端情况下会栈溢出”这句话这能体现你对底层原理的理解。3.4 排查清单一份速查表拿一张排查表给你遇到运行时错误可以按顺序自查。我以前调试二叉树题目时就是靠这份清单一步步定位问题的。序号检查项说明1递归终止条件是否存在函数入口是否处理了root nullptr2是否访问空指针的成员root-left前确认root非空3递归返回值是否一致每个分支返回的语义是否都是“深度”4层序遍历的 q.size() 是否被动态修改进入循环前先存一份 size5迭代栈是否处理了父子节点入栈顺序是否遗漏了左右孩子非空判断6递归深度是否可能过大树是否退化为链表是否改迭代这张表不只适用于最大深度这道题几乎能套用到所有二叉树题目上。我后来刷二叉树的遍历、路径总和、最近公共祖先这些题时也一直用它来定位问题。4. 延伸从深度到遍历、二叉树到二叉搜索树4.1 深度、高度、层数别搞混很多新手会把“深度”和“高度”混用实际上在数据结构里这两个概念有细微差别。节点的深度从根节点到该节点的最长路径上的节点数或边数根节点深度为 1按节点数计。节点的高度从该节点到最远叶子节点的最长路径上的节点数叶子节点高度为 1。整棵树的高度根节点的高度数值上等于整棵树的最大深度。所以你发现没有对一棵树而言“树的高度”和“树的最大深度”是同一个值。但某棵子树的根节点的深度编号和它的高度不一定是同一个数。比如根节点的右孩子它的深度是 2但它的高度可能是 3。搞清这两个概念能避免你在做“判断平衡二叉树”这类题时思路混乱。层数这个概念就更直观了根节点算第 1 层往下递增。层序遍历天然按层组织所以 BFS 解法里数循环次数就是数层数非常自然。4.2 遍历方式与深度的关系二叉树有四种常见遍历方式前序遍历、中序遍历、后序遍历、层序遍历。前三种属于深度优先搜索DFS第四种属于广度优先搜索BFS。求最大深度时DFS 和 BFS 都能做但思路不一样。DFS 沿着一条路径走到黑走完左子树再退回来走右子树通过递归返回值的方式层层汇总。BFS 一层一层扫层数就等于深度。如果你理解了遍历方式做题时会少走很多弯路。比如“二叉树的最小深度”这道题BFS 会更高效因为你从上往下扫遇到第一个叶子节点时就可以直接返回不需要遍历整棵树。而递归 DFS 则需要左右子树都算完再比较效率上不如 BFS 剪枝来得快。再比如“二叉树的最大深度”如果只知道递归模板而不知道层序遍历那面试官让你写迭代版本时就会卡壳。所以我建议刷二叉树题目时每个经典题都争取想出两种解法一种递归、一种迭代。这样对树的两种扫描方式都会形成肌肉记忆。4.3 二叉搜索树与平衡问题聊到树的深度就绕不开二叉搜索树BST和平衡二叉树的关系。二叉搜索树的定义是左子树所有节点的值都小于根节点右子树所有节点的值都大于根节点左右子树也各自是二叉搜索树。BST 的查找效率严重依赖树的深度。如果一棵 BST 是平衡的查找时间复杂度是 O(log n)如果它退化成了一条链查找时间复杂度就变成 O(n)跟线性查找没区别。这就是为什么 AVL 树、红黑树这些自平衡二叉树会被设计出来。它们的核心工作之一就是通过旋转操作保持树的高度在 O(log n) 级别。回到“最大深度”这道题上如果你刷完这道题之后想继续深入可以顺手刷一下“判断平衡二叉树”LeetCode 110和“将有序数组转换为二叉搜索树”LeetCode 108。这两道题一个让你判断树的深度差是否合理一个让你构建出高度平衡的 BST正好把今天学的深度概念用起来。4.4 线索二叉树与Morris遍历有些资料会提到线索二叉树Threaded Binary Tree这个概念经常让初学者犯迷糊。线索二叉树的本质是利用二叉树中的空指针把它们改成指向遍历序列的前驱或后继节点的指针从而让遍历不需要栈和递归就能线性完成。以一个中序遍历的线索二叉树为例如果某个节点没有左孩子它的左指针就指向中序序列的前驱如果没有右孩子它的右指针就指向中序序列的后继。这么做的目的是节省遍历过程中维护栈的开销。这和最大深度有什么关系关系不算直接但它是二叉树知识体系的一部分。如果你理解了线索二叉树的动机你就能理解 Morris 遍历为什么能做到 O(1) 空间复杂度——本质上是临时把空指针利用起来构建一种“动态线索”遍历完再把树恢复原样。我建议初学者先掌握递归和迭代遍历暂时不需要深挖 Morris 遍历。等你对树的指针操作已经非常熟练时再学会顺畅很多。5. 刷题心得与后续扩展5.1 面试中这道题怎么考“二叉树的最大深度”在面试中通常不会单独作为难题出现它更多是被当成一个基础验证题。我遇到过几种典型问法。第一种是热身题面试官让你三分钟写出来考察你的编码习惯和边界意识。这时候递归版本就够了但写的过程中要注意不能有语法错误不能忘记处理空指针。第二种是追问优化面试官会让你不用递归实现或者问你“如果树特别深会怎样”。这时候你把 BFS 版本拿出来顺带解释一下递归的局限性分数会好看不少。第三种是变形题面试官会把最大深度改成最小深度、直径、路径总和等变体。这时候如果你对深度这个概念理解透彻举一反三写代码不会太难。还有一点值得注意写代码时一定要在开始写之前先想清楚终止条件。我见过很多候选人拿到题就敲代码敲完发现没有终止条件再补一个进去整个递归结构就变得很混乱。先想清楚再动手是区分老手和新手的一个明显标志。5.2 三个台阶背模板到真正理解学这道题通常会经历三个阶段。第一阶段套模板。看到二叉树题目就从递归三要素下手先写终止条件再写递归调用最后写返回值。这个阶段的特征是你知道这么写能过但说不清为什么。第二阶段画递归树。每做一道题都在纸上画出递归的压栈和弹栈过程手动模拟一遍。这个阶段你会逐渐理解返回值的传递路径比如leftDepth和rightDepth是怎么一步步汇总到根节点的。第三阶段多解法对比。对同一个题目分别用递归、BFS、迭代 DFS 实现并比较它们的时空复杂度。到这个阶段你就不再是“背题”而是真正理解了树的遍历本质。我自己带过几个朋友刷题发现大多数人卡在第一阶段到第二阶段之间。突破的关键不是多刷题而是停下来手动模拟一遍递归过程。做题慢一点不丢人能讲清楚代码每一步在干什么比一天刷十道但说不明白要强得多。5.3 后续扩展练习刷完最大深度之后我建议按下面的顺序继续往深处扩展每一步都建立在前一步的基础上。LeetCode 110 平衡二叉树判断左右子树深度差是否不超过 1需要自底向上计算高度。LeetCode 111 二叉树的最小深度注意最小深度是到最近叶子节点处理单边子树时要格外小心。LeetCode 543 二叉树的直径直径等于任意两个节点之间最长路径上的边数通常是左右子树深度之和的最大值。LeetCode 104 的姊妹题二叉树的最大路径和、路径总和系列都是从深度出发扩展到路径问题。这几道题刷下来你会形成一套处理二叉树问题的“组合拳”递归返回值怎么设计、全局变量怎么维护、迭代遍历怎么改写成 BFS 或栈模拟。这些能力在后续刷图的题目时同样能迁移过去。最后再分享一个我个人的小习惯每次写完二叉树的递归代码我会手动挑一个特殊输入验证一遍通常是空树和单节点树。这两个输入能最快暴露终止条件的问题。实测下来这个习惯帮我避免了很多次提交后才发现低级错误的尴尬时刻。二叉树这板块细心比聪明更值钱。