1. 先搞清楚这道题到底要我们算什么看到“P4913【深基16.例3】二叉树深度”这个标题第一反应是这不就是递归求树高吗确实核心考点就是二叉树深度。但它把二叉树用一种“很不直观”的方式塞给了你——不用指针不用邻接表直接用 n 行左右儿子编号描述一棵树。很多初学者就是卡在这一步代码逻辑写对了输入处理错了或者数组越界直接报运行时错误然后开始怀疑人生。先还原题目本身。输入第一行给出结点总数 n接下来 n 行第 i 行有两个整数 l_i 和 r_i分别代表结点 i 的左儿子编号和右儿子编号0 表示没有对应儿子。结点编号从 1 到 n。要求输出的是这棵二叉树的深度。这里要特别注意定义根结点位于第 1 层深度等于根结点到最远叶子结点的层数。换句话说输出一个整数代表这棵树总共有多少层。举一个最简单的例子。输入3 2 3 0 0 0 0三行分别描述结点 1、2、3。结点 1 的左儿子是 2右儿子是 3结点 2 和 3 都是叶子。从 1 到叶子一共两层答案是 2。这题适合谁刚学树结构的初学者准备 CSP-J/S 或者 NOIP 的选手以及所有想在“静态建树”上补课的人。它的价值在于把“树的存储”和“递归遍历”两个基本功一次性练到位。后面很多题目比如求二叉树直径、判断平衡二叉树、树上 DFS、最近公共祖先都以这套代码为起点。所以别看它是个“基础例题”把每个细节抠透后面能省很多麻烦。先给结论网上绝大多数题解用的是递归思路很清晰但洛谷这题的数据范围其实会让裸递归在极限数据下爆栈。我第一次刷这道题就吃了这个亏后来带学生也看到有人连续栽在同一个坑里。所以这篇博文会给你两份代码一份递归版方便理解思路一份迭代版确保万无一失。两份你都留好比赛的时候就知道该选哪份了。2. 深度公式是怎么来的从树的递归定义说起2.1 树的递归定义是理解一切的关键树结构最优雅的一点是它天然支持递归定义一棵二叉树要么是空树要么是一个根结点加上两棵互不相交的子树。这个定义听起来像废话但它直接给了我们计算深度的公式。把问题缩小。一棵树的深度等于“它的左右子树中更深的那棵的深度再加上根结点自己这一层”。注意这里已经暗示了左右子树各自也适用同样的规则。一直往下拆拆到空树就得停下来空树没有结点深度是 0。用生活化类比你在数一个家族最长有多少代。从始祖开始已知每个人有两个子女位置。要想知道整个家族最长多少代只需分别数两个分支各自最长多少代取较大者再把始祖这一代加进去。空位置就是 0 代。这个思路几乎可以照搬到代码里。用符号表示就是depth(node) 0, node 不存在时 depth(node) 1 max(depth(left), depth(right)), node 存在时对叶子结点验证一下叶子没有左右儿子两个都是空树depth 都是 0所以叶子深度是 1 max(0, 0) 1。这与“叶子在第 1 层”一致。2.2 推演一个稍微复杂的例子理解公式最好的方式是手算一遍。假设输入5 2 3 4 5 0 0 0 0 0 0结构是1 的左儿子 2右儿子 3结点 2 的左儿子 4右儿子 53 是叶子4、5 是叶子。从 4 开始depth(4) 1 max(0, 0) 1。depth(5) 1。于是 depth(2) 1 max(1, 1) 2。而 depth(3) 1。最外层 depth(1) 1 max(2, 1) 3。答案就是 3。整个过程只需要从叶子向上逐层“返回值”没有任何悬念。这里其实藏着一个重要的编程思维递归并不需要你手动去模拟整棵树的调用顺序你只要保证“当前结点的答案可以由左右子树的答案正确组合”递归会自动帮你把复杂问题拆干净。很多同学写递归时心里发慌总想用大脑跑完所有递归栈其实没必要。你只需要信任递推公式本身再确保基准情况正确。2.3 复杂度分析为什么一个深度问题能做到 O(n)每个结点在递归过程中都会被访问一次每次访问只做常数次比较和加法所以时间复杂度是 O(n)。空间方面递归版会占用函数调用栈栈深度等于树的深度如果一个完全二叉树有 n 个结点深度是 log2(n1) 量级非常安全但如果是一条链每个结点只有一个儿子深度就是 n这就要小心了。n 到 10^6 量级时递归爆栈不是小概率事件而是必然事件。迭代版的空间也类似显式栈里最多存一整层的结点链状时栈大小同样会到 n但这里用的是程序自己管理的堆内存不受系统调用栈限制安全得多。这也是为什么我建议你在写递归版的同时必须掌握迭代版。3. 两份完整代码递归版与迭代版3.1 存储结构为什么用结构体数组而不是指针竞赛里建二叉树最忌讳的就是用指针一个个 new 结点。原因有两个第一n 可能达到 10^6new 一个结点就是一次堆分配分配 10^6 次时间开销大还有内存碎片第二指针容易写错稍不注意就是空指针访问报出不明不白的运行时错误。更靠谱的做法是“静态存储”用一个结构体数组或者两个平行数组 left[]、right[]。每个结点就是一个数组下标结点 i 的左儿子编号存到 left[i]右儿子编号存到 right[i]。“后继关系”由整数编号表达跳过所有指针操作。我推荐用一个结构体数组因为当题目后续需要加字段比如权值、标记时扩展更加自然struct Node { int left, right; } tree[1000005];数组大小为什么开到 1000005因为 n 最大是 10^6开成 1000005 会留一点余量防止某些极端边界访问越界。这是竞赛里的习惯数组尽量开大一点点但别大到爆内存。3.2 递归版代码直击公式#include bits/stdc.h using namespace std; struct Node { int left, right; } tree[1000005]; int dfs(int root) { if (root 0) return 0; return max(dfs(tree[root].left), dfs(tree[root].right)) 1; } int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin n; for (int i 1; i n; i) { cin tree[i].left tree[i].right; } cout dfs(1) \n; return 0; }代码量很少但每一行都值得说清楚。dfs是递归函数参数 root 是当前所在结点的编号。root 等于 0 表示空结点返回 0这是递归的基准情况。向左子树和右子树各自递归取较大值后加 1这就是递推公式的直接实现。main 函数中用ios::sync_with_stdio(false)和cin.tie(0)加速输入输出n 最大能到 10^6关闭同步能省下不少时间。注意输入循环从 1 开始到 n因为结点编号就是 1 到 n。数组的 0 号位留空用来表示空树也避免了结构性浪费。3.3 迭代版代码彻底摆脱爆栈烦恼用显式栈来模拟递归过程。栈里存的不是单个结点而是“结点编号 它当前所在的深度层级”。遍历时每次弹出一个结点更新最大深度再把非空的左右儿子压入栈。因为左右儿子位于下一层深度要在父结点基础上加 1。#include bits/stdc.h using namespace std; struct Node { int left, right; } tree[1000005]; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin n; for (int i 1; i n; i) { cin tree[i].left tree[i].right; } int ans 1; stackpairint, int st; st.push({1, 1}); while (!st.empty()) { auto cur st.top(); st.pop(); int u cur.first; int depth cur.second; ans max(ans, depth); if (tree[u].left ! 0) { st.push({tree[u].left, depth 1}); } if (tree[u].right ! 0) { st.push({tree[u].right, depth 1}); } } cout ans \n; return 0; }这段代码的运行逻辑非常容易理解根结点深度为 1压入栈只要栈不空就弹出并处理把子结点以“深度1”的信息压回去。由于每次更新的 ans 都是当前遇到的结点最大深度循环结束时 ans 就是整棵树的深度。这个写法即使在链状二叉树里也稳稳当当不用担心系统栈溢出。如果你更喜欢 BFS 的层序思路可以用队列替代栈。BFS 每遍历完一层层数计数器加 1最终同样能拿到深度。两种迭代方案选哪个都行栈方案写法更接近递归的 DFS 思路队列方案语义更贴近“层数”的概念。我通常用栈因为代码里能顺便记录每个结点的深度灵活性更高。3.4 从递归版到迭代版思维方式转变初学者最容易犯的问题不是写不出递归而是“递归能写但看不懂”。迭代版迫使你把递归隐式维护的东西显式化栈里的每个元素其实就是递归函数的一次调用参数。递归函数的返回体是“取 max 再 1”迭代版则用 ans 这个全局变量记录最大深度。两者本质上表达的是同一件事只是控制流的表现形式不同。我建议初学者这样过渡先读懂递归版把递推公式写在自己的草稿纸上然后抄一遍迭代版运行几个小样例用断点观察 push 和 pop 的过程。当你能清楚地解释“为什么每次 push 子结点时 depth 是父结点 depth1”你的树形 DFS 基础就算是打牢了。4. 那些年我们一起踩过的坑常见错误与排查实录4.1 运行时错误第一元凶数组越界很多人在本地测试小数据时一切正常一提交就报“运行时错误”第一反应是“数据有毒”。实际上最常见的原因就是数组开小了。这道题 n 最大是 10^6但不少人习惯性地写tree[100000]少了两个零循环读到 tree[n] 的时候就踩到了未分配的内存程序直接崩溃。排查方法很简单检查数组声明大小是否 n 的最大值。这道题开tree[1000005]就行。但开了大数组还有一个隐患如果数组是局部变量比如放在 main 函数内部栈区可能放不下 10^6 个结构体一样会崩。解决方法是把数组放在全局区。上面的两份代码都把 tree 放在了全局位置这是有意为之不只是代码风格问题。// 错误示例数组开在 main 内部 int main() { Node tree[1000005]; // 大约需要 8MB局部栈很可能不够 }4.2 访问 0 号结点别把空树当成普通结点代码里我们用 0 代表“没有儿子”。但很多同学会在递归函数里写if (tree[root].left 0) { // 特判 }这种写法本身没错但有人会在特判之后继续访问tree[0].left于是 0 号结点被当成了真实结点。更隐蔽的错误是迭代版里忘记判断left ! 0直接把 0 号结点压进栈。0 号结点的 left 和 right 都是 0它会被当成一个不断“生育”的无限结点程序陷入死循环直到内存耗尽。解决办法就一句话压栈前和递归前都检查儿子是否为 0。上面给的递归代码干脆不特判直接用root 0作为递归边界把 0 号结点的处理统一收口。这比到处判断left ! 0干净得多也不容易漏。4.3 深度从 0 开始还是从 1 开始这个坑看着幼稚但每年都有不少人翻车。有的教材把根结点深度定义为 0于是整棵树的深度就是“最大路径上的边数”。但这道题按洛谷的习惯根结点在第 1 层所以答案必须是“最大路径上的结点数”。链状的三个结点答案应该是 3而不是 2。题目描述中的“深度”在洛谷的多数题目里都约定根为 1。但也有例外所以每做一道题都要先看样例尤其是边界样例。如果你发现答案始终差 1优先考虑是不是深度定义搞反了。递归版的基准情况也对应着这个定义空树返回 0叶子返回 1这就保证了根结点在第 1 层。4.4 链状二叉树10^6 层递归直接爆栈递归代码在链状数据面前会原形毕露。假设每个结点都只有右儿子整棵树是一条长度 10^6 的链。递归版会连续调用 10^6 层 dfs每一层都占用系统栈空间。大多数 OJ 给进程的栈空间是 8MB 左右超出后立刻段错误表现也是“运行时错误”。这个问题在本地不一定能复现因为本机栈空间和设备环境不同这就更危险。解法就是换成第 3 节给的迭代版。显式栈使用堆内存链状情况下虽然栈里也会积累 10^6 个元素但堆空间远大于系统栈内存占用也只会在个位数 MB 级别安全得多。4.5 输入输出性能n10^6 时别偷懒如果不用ios::sync_with_stdio(false)在 n10^6 量级下 cin 会明显变慢有些比较严格的数据可能直接 TLE。这是竞赛选手的基本操作。输出用\n而不是endl因为 endl 还要额外刷新缓冲区频繁刷新在输出量大时会有性能损耗。上面代码里我两处都做了属于不用动脑的常规优化。调试小技巧在本地写一个数据生成器专门生成单链和完全二叉树两种极端形态用迭代版跑一遍再把递归版也跑一遍。同样的输入两个版本答案必须一样。这样既能验证正确性又能直观感受爆栈问题。这个习惯我带学生时反复强调比盲目提交试错高效太多。5. 从“二叉树深度”延伸出去遍历和进阶题目5.1 求深度本质上是后序遍历你可能没注意求深度的递归顺序和二叉树后序遍历的“左右根”顺序是完全一致的。先递归左子树再递归右子树最后用左右子树的返回值计算当前结点。只是这道题不需要做额外输出只返回一个整数所以看起来不像遍历。理解了这一点你就能把深度、结点计数、叶子计数、是否平衡这些问题统一到一个框架里都是“自底向上收集子树信息再汇总到当前结点”。学到这里就形成了一个能力迁移点。以后再遇到“返回子树里的最大路径和”“统计每个子树内满足条件的结点个数”这类问题你会觉得很眼熟因为它们都是同一种 DFS 形态。5.2 深度是很多树的进阶题的地基掌握了最深路径你就已经具备了解一批“树形题目”的底层能力。随便举几个二叉树直径就是树上两个叶子之间距离的最大值。解法之一是在求深度的递归里同时维护“左子树深度 右子树深度 1”把它作为经过当前结点的候选直径。平衡二叉树判断判断任意结点的左右子树深度差是否不超过 1。还是递归但递归需要同时返回“当前子树是否平衡”和“当前子树深度”用深度差判断。二叉树最大宽度这个就更贴近 BFS 了用层序遍历记录每一层的结点个数。最近的公共祖先可以先预处理每个结点的父节点信息再用深度把两个结点对齐到同一层最后同步向上跳。这些题刷多了你会发现深度这个指标就像树的“质量秤”所有稍微复杂的树上信息最终都要先知道子树的高度才能继续往下算。5.3 工程里的“树深度”同样重要别以为“树深”只是竞赛题概念。现实中你在写的项目几乎天天在跟树深打交道JSON 配置文件的嵌套层数、XML/HTML 的 DOM 树层级、文件系统目录的深度甚至压缩包内文件路径层级都有树的影子。处理这些数据时计算最大嵌套深度用的核心逻辑和本题几乎一模一样只是把left/right换成了children列表。比如一个 JSON 嵌套很深的外部输入如果程序按递归方式解析同样会爆栈。成熟的解析器会限制最大嵌套深度或者把递归解析改成显式栈的迭代解析。所以你在竞赛里养成的“别裸递归到底”的习惯在工业代码里同样救过不少人。别觉得这是刷题无用论的反例恰恰相反它是刷题刷到点子上的证据。6. 实战建议与个人体会最后还是那句老话光看不写等于白学。这道 P4913 题目小但五脏俱全我建议你按这个顺序做一遍先用递归版写出并 AC再手动构造一条长链看递归版会不会爆栈接着改写成迭代版再次 AC并对比两份代码的时间和内存差异。有一件事我这些年带的每个学生都遇到过我也跟你明说递归版确实好写但如果你没理解“为什么空树是 0叶子是 1”那即使 AC 了下一道树形题依然会卡住。反过来如果你能把迭代版讲给别人听你的树形 DFS 基本功才真正过关。另外一个小技巧看样例之外自己再构造三个测试点只有根结点、完全二叉树、单链。三个答案分别是 1、树高、n。花不了两分钟但能覆盖掉一大半的边界错误。除了写题还可以顺手把这道题用 Python、Java 各写一遍比较不同语言的递归栈限制差异。Python 的默认递归深度更低深链数据用递归很容易直接报错这时候你就更能体会到“迭代版才是通用解法”这句话的分量。最后再分享一个我自己的习惯凡是涉及树的题我开数组一律比 n 多开 5 到 10 个位置绝不写刚刚好。这不是洁癖而是为了把数组越界这种低级错误的概率降到零。这个习惯帮我省下的挣扎时间远比我“浪费”的那一点内存值钱。
P4913二叉树深度：递归与迭代实现及爆栈避坑指南
1. 先搞清楚这道题到底要我们算什么看到“P4913【深基16.例3】二叉树深度”这个标题第一反应是这不就是递归求树高吗确实核心考点就是二叉树深度。但它把二叉树用一种“很不直观”的方式塞给了你——不用指针不用邻接表直接用 n 行左右儿子编号描述一棵树。很多初学者就是卡在这一步代码逻辑写对了输入处理错了或者数组越界直接报运行时错误然后开始怀疑人生。先还原题目本身。输入第一行给出结点总数 n接下来 n 行第 i 行有两个整数 l_i 和 r_i分别代表结点 i 的左儿子编号和右儿子编号0 表示没有对应儿子。结点编号从 1 到 n。要求输出的是这棵二叉树的深度。这里要特别注意定义根结点位于第 1 层深度等于根结点到最远叶子结点的层数。换句话说输出一个整数代表这棵树总共有多少层。举一个最简单的例子。输入3 2 3 0 0 0 0三行分别描述结点 1、2、3。结点 1 的左儿子是 2右儿子是 3结点 2 和 3 都是叶子。从 1 到叶子一共两层答案是 2。这题适合谁刚学树结构的初学者准备 CSP-J/S 或者 NOIP 的选手以及所有想在“静态建树”上补课的人。它的价值在于把“树的存储”和“递归遍历”两个基本功一次性练到位。后面很多题目比如求二叉树直径、判断平衡二叉树、树上 DFS、最近公共祖先都以这套代码为起点。所以别看它是个“基础例题”把每个细节抠透后面能省很多麻烦。先给结论网上绝大多数题解用的是递归思路很清晰但洛谷这题的数据范围其实会让裸递归在极限数据下爆栈。我第一次刷这道题就吃了这个亏后来带学生也看到有人连续栽在同一个坑里。所以这篇博文会给你两份代码一份递归版方便理解思路一份迭代版确保万无一失。两份你都留好比赛的时候就知道该选哪份了。2. 深度公式是怎么来的从树的递归定义说起2.1 树的递归定义是理解一切的关键树结构最优雅的一点是它天然支持递归定义一棵二叉树要么是空树要么是一个根结点加上两棵互不相交的子树。这个定义听起来像废话但它直接给了我们计算深度的公式。把问题缩小。一棵树的深度等于“它的左右子树中更深的那棵的深度再加上根结点自己这一层”。注意这里已经暗示了左右子树各自也适用同样的规则。一直往下拆拆到空树就得停下来空树没有结点深度是 0。用生活化类比你在数一个家族最长有多少代。从始祖开始已知每个人有两个子女位置。要想知道整个家族最长多少代只需分别数两个分支各自最长多少代取较大者再把始祖这一代加进去。空位置就是 0 代。这个思路几乎可以照搬到代码里。用符号表示就是depth(node) 0, node 不存在时 depth(node) 1 max(depth(left), depth(right)), node 存在时对叶子结点验证一下叶子没有左右儿子两个都是空树depth 都是 0所以叶子深度是 1 max(0, 0) 1。这与“叶子在第 1 层”一致。2.2 推演一个稍微复杂的例子理解公式最好的方式是手算一遍。假设输入5 2 3 4 5 0 0 0 0 0 0结构是1 的左儿子 2右儿子 3结点 2 的左儿子 4右儿子 53 是叶子4、5 是叶子。从 4 开始depth(4) 1 max(0, 0) 1。depth(5) 1。于是 depth(2) 1 max(1, 1) 2。而 depth(3) 1。最外层 depth(1) 1 max(2, 1) 3。答案就是 3。整个过程只需要从叶子向上逐层“返回值”没有任何悬念。这里其实藏着一个重要的编程思维递归并不需要你手动去模拟整棵树的调用顺序你只要保证“当前结点的答案可以由左右子树的答案正确组合”递归会自动帮你把复杂问题拆干净。很多同学写递归时心里发慌总想用大脑跑完所有递归栈其实没必要。你只需要信任递推公式本身再确保基准情况正确。2.3 复杂度分析为什么一个深度问题能做到 O(n)每个结点在递归过程中都会被访问一次每次访问只做常数次比较和加法所以时间复杂度是 O(n)。空间方面递归版会占用函数调用栈栈深度等于树的深度如果一个完全二叉树有 n 个结点深度是 log2(n1) 量级非常安全但如果是一条链每个结点只有一个儿子深度就是 n这就要小心了。n 到 10^6 量级时递归爆栈不是小概率事件而是必然事件。迭代版的空间也类似显式栈里最多存一整层的结点链状时栈大小同样会到 n但这里用的是程序自己管理的堆内存不受系统调用栈限制安全得多。这也是为什么我建议你在写递归版的同时必须掌握迭代版。3. 两份完整代码递归版与迭代版3.1 存储结构为什么用结构体数组而不是指针竞赛里建二叉树最忌讳的就是用指针一个个 new 结点。原因有两个第一n 可能达到 10^6new 一个结点就是一次堆分配分配 10^6 次时间开销大还有内存碎片第二指针容易写错稍不注意就是空指针访问报出不明不白的运行时错误。更靠谱的做法是“静态存储”用一个结构体数组或者两个平行数组 left[]、right[]。每个结点就是一个数组下标结点 i 的左儿子编号存到 left[i]右儿子编号存到 right[i]。“后继关系”由整数编号表达跳过所有指针操作。我推荐用一个结构体数组因为当题目后续需要加字段比如权值、标记时扩展更加自然struct Node { int left, right; } tree[1000005];数组大小为什么开到 1000005因为 n 最大是 10^6开成 1000005 会留一点余量防止某些极端边界访问越界。这是竞赛里的习惯数组尽量开大一点点但别大到爆内存。3.2 递归版代码直击公式#include bits/stdc.h using namespace std; struct Node { int left, right; } tree[1000005]; int dfs(int root) { if (root 0) return 0; return max(dfs(tree[root].left), dfs(tree[root].right)) 1; } int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin n; for (int i 1; i n; i) { cin tree[i].left tree[i].right; } cout dfs(1) \n; return 0; }代码量很少但每一行都值得说清楚。dfs是递归函数参数 root 是当前所在结点的编号。root 等于 0 表示空结点返回 0这是递归的基准情况。向左子树和右子树各自递归取较大值后加 1这就是递推公式的直接实现。main 函数中用ios::sync_with_stdio(false)和cin.tie(0)加速输入输出n 最大能到 10^6关闭同步能省下不少时间。注意输入循环从 1 开始到 n因为结点编号就是 1 到 n。数组的 0 号位留空用来表示空树也避免了结构性浪费。3.3 迭代版代码彻底摆脱爆栈烦恼用显式栈来模拟递归过程。栈里存的不是单个结点而是“结点编号 它当前所在的深度层级”。遍历时每次弹出一个结点更新最大深度再把非空的左右儿子压入栈。因为左右儿子位于下一层深度要在父结点基础上加 1。#include bits/stdc.h using namespace std; struct Node { int left, right; } tree[1000005]; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin n; for (int i 1; i n; i) { cin tree[i].left tree[i].right; } int ans 1; stackpairint, int st; st.push({1, 1}); while (!st.empty()) { auto cur st.top(); st.pop(); int u cur.first; int depth cur.second; ans max(ans, depth); if (tree[u].left ! 0) { st.push({tree[u].left, depth 1}); } if (tree[u].right ! 0) { st.push({tree[u].right, depth 1}); } } cout ans \n; return 0; }这段代码的运行逻辑非常容易理解根结点深度为 1压入栈只要栈不空就弹出并处理把子结点以“深度1”的信息压回去。由于每次更新的 ans 都是当前遇到的结点最大深度循环结束时 ans 就是整棵树的深度。这个写法即使在链状二叉树里也稳稳当当不用担心系统栈溢出。如果你更喜欢 BFS 的层序思路可以用队列替代栈。BFS 每遍历完一层层数计数器加 1最终同样能拿到深度。两种迭代方案选哪个都行栈方案写法更接近递归的 DFS 思路队列方案语义更贴近“层数”的概念。我通常用栈因为代码里能顺便记录每个结点的深度灵活性更高。3.4 从递归版到迭代版思维方式转变初学者最容易犯的问题不是写不出递归而是“递归能写但看不懂”。迭代版迫使你把递归隐式维护的东西显式化栈里的每个元素其实就是递归函数的一次调用参数。递归函数的返回体是“取 max 再 1”迭代版则用 ans 这个全局变量记录最大深度。两者本质上表达的是同一件事只是控制流的表现形式不同。我建议初学者这样过渡先读懂递归版把递推公式写在自己的草稿纸上然后抄一遍迭代版运行几个小样例用断点观察 push 和 pop 的过程。当你能清楚地解释“为什么每次 push 子结点时 depth 是父结点 depth1”你的树形 DFS 基础就算是打牢了。4. 那些年我们一起踩过的坑常见错误与排查实录4.1 运行时错误第一元凶数组越界很多人在本地测试小数据时一切正常一提交就报“运行时错误”第一反应是“数据有毒”。实际上最常见的原因就是数组开小了。这道题 n 最大是 10^6但不少人习惯性地写tree[100000]少了两个零循环读到 tree[n] 的时候就踩到了未分配的内存程序直接崩溃。排查方法很简单检查数组声明大小是否 n 的最大值。这道题开tree[1000005]就行。但开了大数组还有一个隐患如果数组是局部变量比如放在 main 函数内部栈区可能放不下 10^6 个结构体一样会崩。解决方法是把数组放在全局区。上面的两份代码都把 tree 放在了全局位置这是有意为之不只是代码风格问题。// 错误示例数组开在 main 内部 int main() { Node tree[1000005]; // 大约需要 8MB局部栈很可能不够 }4.2 访问 0 号结点别把空树当成普通结点代码里我们用 0 代表“没有儿子”。但很多同学会在递归函数里写if (tree[root].left 0) { // 特判 }这种写法本身没错但有人会在特判之后继续访问tree[0].left于是 0 号结点被当成了真实结点。更隐蔽的错误是迭代版里忘记判断left ! 0直接把 0 号结点压进栈。0 号结点的 left 和 right 都是 0它会被当成一个不断“生育”的无限结点程序陷入死循环直到内存耗尽。解决办法就一句话压栈前和递归前都检查儿子是否为 0。上面给的递归代码干脆不特判直接用root 0作为递归边界把 0 号结点的处理统一收口。这比到处判断left ! 0干净得多也不容易漏。4.3 深度从 0 开始还是从 1 开始这个坑看着幼稚但每年都有不少人翻车。有的教材把根结点深度定义为 0于是整棵树的深度就是“最大路径上的边数”。但这道题按洛谷的习惯根结点在第 1 层所以答案必须是“最大路径上的结点数”。链状的三个结点答案应该是 3而不是 2。题目描述中的“深度”在洛谷的多数题目里都约定根为 1。但也有例外所以每做一道题都要先看样例尤其是边界样例。如果你发现答案始终差 1优先考虑是不是深度定义搞反了。递归版的基准情况也对应着这个定义空树返回 0叶子返回 1这就保证了根结点在第 1 层。4.4 链状二叉树10^6 层递归直接爆栈递归代码在链状数据面前会原形毕露。假设每个结点都只有右儿子整棵树是一条长度 10^6 的链。递归版会连续调用 10^6 层 dfs每一层都占用系统栈空间。大多数 OJ 给进程的栈空间是 8MB 左右超出后立刻段错误表现也是“运行时错误”。这个问题在本地不一定能复现因为本机栈空间和设备环境不同这就更危险。解法就是换成第 3 节给的迭代版。显式栈使用堆内存链状情况下虽然栈里也会积累 10^6 个元素但堆空间远大于系统栈内存占用也只会在个位数 MB 级别安全得多。4.5 输入输出性能n10^6 时别偷懒如果不用ios::sync_with_stdio(false)在 n10^6 量级下 cin 会明显变慢有些比较严格的数据可能直接 TLE。这是竞赛选手的基本操作。输出用\n而不是endl因为 endl 还要额外刷新缓冲区频繁刷新在输出量大时会有性能损耗。上面代码里我两处都做了属于不用动脑的常规优化。调试小技巧在本地写一个数据生成器专门生成单链和完全二叉树两种极端形态用迭代版跑一遍再把递归版也跑一遍。同样的输入两个版本答案必须一样。这样既能验证正确性又能直观感受爆栈问题。这个习惯我带学生时反复强调比盲目提交试错高效太多。5. 从“二叉树深度”延伸出去遍历和进阶题目5.1 求深度本质上是后序遍历你可能没注意求深度的递归顺序和二叉树后序遍历的“左右根”顺序是完全一致的。先递归左子树再递归右子树最后用左右子树的返回值计算当前结点。只是这道题不需要做额外输出只返回一个整数所以看起来不像遍历。理解了这一点你就能把深度、结点计数、叶子计数、是否平衡这些问题统一到一个框架里都是“自底向上收集子树信息再汇总到当前结点”。学到这里就形成了一个能力迁移点。以后再遇到“返回子树里的最大路径和”“统计每个子树内满足条件的结点个数”这类问题你会觉得很眼熟因为它们都是同一种 DFS 形态。5.2 深度是很多树的进阶题的地基掌握了最深路径你就已经具备了解一批“树形题目”的底层能力。随便举几个二叉树直径就是树上两个叶子之间距离的最大值。解法之一是在求深度的递归里同时维护“左子树深度 右子树深度 1”把它作为经过当前结点的候选直径。平衡二叉树判断判断任意结点的左右子树深度差是否不超过 1。还是递归但递归需要同时返回“当前子树是否平衡”和“当前子树深度”用深度差判断。二叉树最大宽度这个就更贴近 BFS 了用层序遍历记录每一层的结点个数。最近的公共祖先可以先预处理每个结点的父节点信息再用深度把两个结点对齐到同一层最后同步向上跳。这些题刷多了你会发现深度这个指标就像树的“质量秤”所有稍微复杂的树上信息最终都要先知道子树的高度才能继续往下算。5.3 工程里的“树深度”同样重要别以为“树深”只是竞赛题概念。现实中你在写的项目几乎天天在跟树深打交道JSON 配置文件的嵌套层数、XML/HTML 的 DOM 树层级、文件系统目录的深度甚至压缩包内文件路径层级都有树的影子。处理这些数据时计算最大嵌套深度用的核心逻辑和本题几乎一模一样只是把left/right换成了children列表。比如一个 JSON 嵌套很深的外部输入如果程序按递归方式解析同样会爆栈。成熟的解析器会限制最大嵌套深度或者把递归解析改成显式栈的迭代解析。所以你在竞赛里养成的“别裸递归到底”的习惯在工业代码里同样救过不少人。别觉得这是刷题无用论的反例恰恰相反它是刷题刷到点子上的证据。6. 实战建议与个人体会最后还是那句老话光看不写等于白学。这道 P4913 题目小但五脏俱全我建议你按这个顺序做一遍先用递归版写出并 AC再手动构造一条长链看递归版会不会爆栈接着改写成迭代版再次 AC并对比两份代码的时间和内存差异。有一件事我这些年带的每个学生都遇到过我也跟你明说递归版确实好写但如果你没理解“为什么空树是 0叶子是 1”那即使 AC 了下一道树形题依然会卡住。反过来如果你能把迭代版讲给别人听你的树形 DFS 基本功才真正过关。另外一个小技巧看样例之外自己再构造三个测试点只有根结点、完全二叉树、单链。三个答案分别是 1、树高、n。花不了两分钟但能覆盖掉一大半的边界错误。除了写题还可以顺手把这道题用 Python、Java 各写一遍比较不同语言的递归栈限制差异。Python 的默认递归深度更低深链数据用递归很容易直接报错这时候你就更能体会到“迭代版才是通用解法”这句话的分量。最后再分享一个我自己的习惯凡是涉及树的题我开数组一律比 n 多开 5 到 10 个位置绝不写刚刚好。这不是洁癖而是为了把数组越界这种低级错误的概率降到零。这个习惯帮我省下的挣扎时间远比我“浪费”的那一点内存值钱。
