企业官网建设流程全解析

刷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; } queue<TreeNode*> 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; } stack<pair<TreeNode*, int>> stk; stk.push({root, 1}); int ans = 0; while (!stk.empty()) { pair<TreeNode*, 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; } };

这里用pair<TreeNode*, 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 排查清单：一份速查表

拿一张排查表给你，遇到运行时错误可以按顺序自查。我以前调试二叉树题目时就是靠这份清单一步步定位问题的。

这张表不只适用于最大深度这道题，几乎能套用到所有二叉树题目上。我后来刷二叉树的遍历、路径总和、最近公共祖先这些题时，也一直用它来定位问题。

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 或栈模拟。这些能力在后续刷图的题目时同样能迁移过去。

最后再分享一个我个人的小习惯：每次写完二叉树的递归代码，我会手动挑一个特殊输入验证一遍，通常是空树和单节点树。这两个输入能最快暴露终止条件的问题。实测下来，这个习惯帮我避免了很多次提交后才发现低级错误的尴尬时刻。二叉树这板块，细心比聪明更值钱。