刷题的人应该都体验过这种情况好不容易看懂了一个知识点结果落到某道题目上第一眼还是不知道代码该从哪一行写起。我当年学二叉树的时候就是被“指针、结构体、递归三件套”劝退过好几回。直到把洛谷 P4913【深基16.例3】二叉树深度认真做透才算把二叉树的底子真正打好。这道题题目不长输入格式也简单但它是很多后续树形问题的地基值得花点时间拆开揉碎讲清楚。这道题本质上就干一件事给你一棵树的每个节点分别指向哪两个儿子让你算这棵树从根到最远叶子有多深。别看它只是个带“例3”的基础题n可以到百万级别光这一个数据规模就能卡掉不少“会写但写得不稳”的代码。所以这篇文章不打算只贴一份能过的题解而是从题意的每个细节、三种不同写法、以及我实际提交过程中踩过的坑完整复盘一遍。适合刚学完树结构、准备练递归和BFS或者想给自己攒一套基础模板的人。1. 题目到底在考什么P4913的核心思路与题意拆解1.1 逐句拆题输入输出的真实含义先看输入格式。第一行一个整数n表示二叉树有n个节点。接下来的n行第i行会有两个整数分别表示编号为i的节点的左儿子和右儿子是谁0就代表这个位置没有儿子。也就是说题目直接给了你一个“编号到左孩子右孩子的映射表”你要根据这张表找到最深的那条路径。根节点的编号是确定的就是1。很多同学第一次碰这种输入会懵怎么不是按层给怎么不告诉我父子关系实际上这就是竞赛里最常见的静态二叉树存储方式数组下标就是节点编号数组的值存孩子编号。不需要指针不需要结构体两个int数组就能装下一整棵树。题目不给你父节点也不给你层序你要自己决定用什么方式从根出发去遍历这是第一层考验。输出就一个整数表示二叉树的深度。注意这里的深度从根开始算根节点自己一层的深度是1不是0。很多题解会踩这个坑下面我会专门讲。1.2 为什么说它是“深基16”里承上启下的例题深基16这一章讲的是二叉树。前面的题目大概率在建树、遍历这些基础操作上铺垫到P4913这里开始用“深度”这个概念把递归和遍历串起来。深度是一个衡量指标但它同时又是很多树形算法的出发点比如判断一棵树平不平衡要先知道左右子树的深度求树的直径要考虑两条最深的路径怎么拼接树形DP更是直接把“子树向上返回信息”当成基本操作来用。所以别把P4913当成一道背答案的模板题。它真正想让你练的是给定父亲到孩子的邻接关系你能不能自然地用递归函数表达“先问左右子树要答案再综合出当前节点的答案”这个思维过程。这个思维过程以后再遇到二叉树问题几乎天天要用。1.3 二叉树深度的两种等价定义选哪一种取决于你的遍历方式二叉树深度有两种常见说法。一种是从根到最远叶子经过的节点数根深度为1另一种是从根到最远叶子的边数这种情况下根深度为0。P4913用的明显是前一种输出样例的答案也从1起算。这不只是文字游戏它直接决定了递归返回结果的写法。如果你写递归那么空节点返回0非空节点的深度就是左右子树深度的最大值再加1。如果你写BFS那么队列每扩展一层深度计数器就加1最后扩展到的层数就是答案。两种定义对应两种代码习惯但算出来的数值在P4913这道题里必须统一。我建议你第一次做的时候先用笔在草稿纸上画一棵只有三个节点的小树分别跑一遍这两种定义确认自己不会在“1”的位置上犯迷糊。2. 三种能过题的写法递归DFS、层序BFS、手写栈迭代2.1 写法一递归DFS主函数短到怀疑人生递归写法大概是整道题最直观的版本。定义一个函数dfs(u)传入节点编号返回这棵子树的深度。如果u是0说明当前没有节点深度为0否则去看左孩子和右孩子分别能给出多深的答案取较大的那个再加1代表把当前这层也算进去。#include bits/stdc.h using namespace std; const int MAXN 1000005; int lc[MAXN], rc[MAXN]; int dfs(int u) { if (u 0) return 0; return max(dfs(lc[u]), dfs(rc[u])) 1; } int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin n; for (int i 1; i n; i) { cin lc[i] rc[i]; } cout dfs(1) \n; return 0; }这段代码的核心只有三行空节点返回0、取左右最大值、加1。我见过不少人把“1”写在max的括号里比如下面这种写法return max(dfs(lc[u]) 1, dfs(rc[u]) 1);这种写法也不是完全不行但写起来冗余而且特别容易忘记对空节点u 0的情况单独处理。一旦空节点返回了1那整棵树的深度都会被多算一层最后答案直接偏大1。我建议还是统一用“空节点返回0非空节点max1”的写法逻辑干净不容易错。递归写法最大的隐患是爆栈。如果n最大到10^6而数据构造出一条特别深的链比如1号节点的左儿子是2号2号的左儿子是3号一直到底那dfs的递归深度也会到10^6量级。默认系统栈很可能扛不住。洛谷的数据不一定会出这种极端链或者评测环境栈空间给得比较足但我不会拿随机数据去赌“应该没事”。想用递归可以心里要清楚这个风险。2.2 写法二层序BFS不靠系统栈链状数据也稳如果不想担心爆栈BFS层序遍历是更稳的选择。思路是先把根节点放进队列然后循环处理当前队列里的所有节点每处理一波深度就加1。处理过程中把每个节点的非空孩子继续放进队列作为下一波要处理的节点。等队列清空深度计数器就是整棵树的深度。#include bits/stdc.h using namespace std; const int MAXN 1000005; int lc[MAXN], rc[MAXN]; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin n; for (int i 1; i n; i) { cin lc[i] rc[i]; } queueint q; q.push(1); int depth 0; while (!q.empty()) { int sz q.size(); depth; while (sz--) { int u q.front(); q.pop(); if (lc[u]) q.push(lc[u]); if (rc[u]) q.push(rc[u]); } } cout depth \n; return 0; }关键点在于先记录q.size()再一次性处理这一层的所有节点。如果你不记录size而是写成while (!q.empty())那depth加几次就不是层数了。这个细节很多人第一次写BFS都会错。我最初也犯过这个毛病以为是每次出队就深度加1结果深度变成了节点数。BFS的另一个好处是天然不会递归爆栈。它是用队列在堆上做“待办清单”树的形状再畸形也只影响队列里同时存在的节点数最多不会超过n量级。所以从稳妥角度看我推荐第一次提交这道题直接用BFS版本。2.3 写法三手写栈模拟DFS被迫防爆栈时的备选方案除了BFS还可以用手写栈把递归改成迭代。原理很简单显式维护一个栈里面放“节点编号”和“到达这个节点时的深度”这一对信息。最开始把根节点和深度1压入栈之后每次弹出一个元素就更新一次答案再把这个节点的孩子以深度加1的状态压入栈。#include bits/stdc.h using namespace std; const int MAXN 1000005; int lc[MAXN], rc[MAXN]; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin n; for (int i 1; i n; i) { cin lc[i] rc[i]; } vectorpairint, int stk; stk.push_back({1, 1}); int ans 1; while (!stk.empty()) { pairint, int cur stk.back(); stk.pop_back(); int u cur.first; int d cur.second; ans max(ans, d); if (lc[u]) stk.push_back({lc[u], d 1}); if (rc[u]) stk.push_back({rc[u], d 1}); } cout ans \n; return 0; }这里用vector当栈因为vector既可以push_back、pop_back也支持直接访问栈顶刷题时比std::stack稍微灵活一点。压栈顺序不影响答案因为我们是把每个节点到根的深度独立记录下来的最后只要取最大值就行。如果你想更严谨地模拟递归调用栈可以增加一个状态字段表示“左子树访问完没有”但本题不需要因为深度这种聚合信息用栈也可以算。手写栈写法在这道题里优势不明显但它是一套通用技能以后遇到那种“递归绝对爆栈但BFS语义又不太匹配”的树形问题可以临时派上用场。3. 过题细节与实战经验确认边界、输入和那些常见的80分原因3.1 不要用指针结构体动态建树静态数组才是竞赛标配我看到过很多刚学二叉树的人一上来就想写结构体加指针再new几个节点出来。这种思路不是不能做但对P4913这种n可以到10^6的题目来说动态分配和散落指针的访问模式会拖慢速度还可能造成不必要的内存碎片。更重要的是指针建树往往还要操心“创建节点”“连接左右孩子”这些和核心算法无关的步骤很容易写着写着就把自己绕进去。竞赛里最常用的二叉树建模方式就是两个数组lc[i]存i号节点的左孩子编号rc[i]存右孩子编号。没孩子就是0。内存方面两个int数组每个数组长度10^6出头总共大约8MB非常轻松。访问方式就是下标直查速度也快。这里补一句内存计算10^6个int约4MB两个数组就是8MB再加上BFS的队列或栈总内存离题目限制还远得很。3.2 读取时用cin还是快读不同情况下的取舍既然n可能到百万输入行数就可能有百万行。cincout不加优化指令时单次输出缓冲刷新和流同步会拖后腿所以要么在main最开头写上ios::sync_with_stdio(false); cin.tie(0);要么直接用scanf和printf。这两者都可以在本题稳过。我个人的习惯是刷洛谷的题只要能过写cin加同步关闭就够。如果你还想要一个保险的通用快读函数可以把这个模板抄进自己的代码库里。它只处理非负整数但本题输入全部是非负的足够用int readInt() { int x 0; char c getchar(); while (c 0 || c 9) c getchar(); while (c 0 c 9) { x x * 10 c - 0; c getchar(); } return x; }这个快读的原理很简单跳过所有非数字字符然后把连续数字拼成整数。别急着在每道题都用它但可以把它当成备份方案。3.3 根节点、空节点、深度起点三个最隐蔽的边界先说空节点。输入里0表示没有儿子所以如果你用if (lc[u])就能很自然地跳过空儿子不需要额外写if (lc[u] ! 0)。这两种写法都可以但前后要统一否则万一某次写成了if (lc[u] 0)就把真正的儿子全跳过了程序会直接得出深度1。这种错误在代码里特别难一眼看出来因为编译不会报错逻辑会跟你预期完全相反。再说根节点。题目明确根是1号节点所以从dfs(1)或q.push(1)开始写。有些类似题目不会固定根会额外给你根节点编号但P4913这里不用做特殊处理。如果你做过的题多了把这题作为模板时要留个心眼别把根写死成习惯。最后是深度起点。递归写法里空节点返回0非空节点max1天然保证根深度为1。BFS写法里depth初始化为0第一次进入while循环就自增为1也对应根节点的深度。如果你把两个写法的语义混着记很容易出现“输出比正确答案少1或多1”的情况。我提供的两个测试数据很好用1 0 0这个数据只有一个根正确输出1。还有3 2 3 0 0 0 0这棵树的根是1左右孩子分别是2和3深度是2。两个数据都跑通了再提交基本不会在边界上翻车。3.4 那些“只拿80分”的常见原因我在刷题的话题里经常看到有人说“为什么我这个只能拿80分”其实这种问题在P4913这种基础题上也存在。排除评测系统本身波动通常来来回回就是下面这几个原因。用递归没开栈空间极端链状数据导致运行时错误可能挂掉一两个点。BFS把size记录漏了depth跟着出队次数涨答案直接变成节点个数最后一个大点必错。读入用endl换行每次换行都刷新一次缓冲区百万级输入下TLE最后两个点。只处理了n0的情况但题目里n显然至少为1没必要特判n0反而可能因为特判写出多余逻辑干扰主流程。数组下标越界比如读入时把lc[i]写成lc[i-1]n大时分配的空间不够访问。这里面最隐蔽的就是BFS忘记size。这个坑我不止一次见人踩过包括我自己第一次写树的层序遍历也犯过。建议把“先取size再处理整层”这句话直接记在注释里。3.5 三种方案的复杂度对比提交前心里有数我把三种方案的时间和空间成本整理成一张表方便直观对比方案时间复杂度空间复杂度是否容易爆系统栈适合场景递归DFSO(n)O(n)递归栈深度取决于树高链状树时风险较高理解递归逻辑数据规模小或随机层序BFSO(n)O(n)队列最多存一层节点不会大多数情况推荐首选手写栈迭代O(n)O(n)vector显式存栈不会栈空间紧张或想练迭代写法时间复杂度都是O(n)因为每个节点只会被访问固定次数。空间上三者也都是O(n)区别在于BFS队列的瞬时峰值一般小于递归栈的瞬时峰值极端链状树尤其明显。如果你在乎常数三者差异其实都不大真正的差异在系统栈的安全性上。4. 复盘与拓展一道基础题如何带出一串后续题4.1 从“深度”到“直径”二叉树问题的常见递进路线求深度这道题学会之后最自然的下一步是求二叉树的直径。直径通常指树上最远两个节点之间的距离。对二叉树来说我们可以换一种视角经过某个节点的最长路径其实就是它左子树深度加上右子树深度。所以在一次递归里同时返回子树的深度和经过该节点的路径长度就能在O(n)内求出直径。洛谷相关的二叉树题目里P3884这类题目就会把深度、宽度、距离这类指标放一起考察。你会发现P4913里练熟的“递归返回子树信息”能力正是做那些题的基本功。我顺便提一个做题方法做完P4913之后不要着急刷下一道先自己改一版代码输出每个节点的深度看看是不是和手算一致。这种“改输入、改输出、再造数据验证”的过程比连刷十道同类型题更训练能力。4.2 从“存储”到“遍历”孩子数组建树后能迁移到哪里去P4913使用的lc/rc数组存储方式可以平滑迁移到很多遍历和重建题。比如给你前序和中序求后序你需要先在数组中定位根的位置再递归处理左右区间给你父节点的孩子编号关系你要能通过递归访问子树。这类题本质上都是“用一个函数传入当前子树的范围或根节点编号递归处理左右部分”。如果你在P4913里真的理解了递归的调用过程再接触P1030这类求先序排列的题时就会觉得只是在原有递归框架里多加了几个参数和输出逻辑。另外我建议把lc/rc数组当成自己的标准模板不要轻易换成vectorvector 存邻接表。邻接表能存二叉树但语义不直观而且vector会有额外的对象开销。两个数组足矣。4.3 建立你自己的刷题模板快读、二叉树深度、BFS层序一把梭在实际比赛或日常刷题时很多代码是可以复用的。我自己的模板里就会长期保留这几个部分一个快读函数、一个lc/rc数组、一个BFS层序函数。遇到二叉树题目先把模板复制过来再根据题意改输入映射和输出指标。这样比每道题从零开始写要快得多。以P4913为例最终我提交用的代码其实是BFS版本因为提交时我不太想赌数据形态。先说结论这个做法在洛谷上能稳定通过而且写起来也很快。平时用来练递归可以用递归版快速提交求稳我用BFS版。#include bits/stdc.h using namespace std; const int MAXN 1000005; int lc[MAXN], rc[MAXN]; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin n; for (int i 1; i n; i) cin lc[i] rc[i]; int ans 0; queueint q; q.push(1); while (!q.empty()) { int sz q.size(); ans; while (sz--) { int u q.front(); q.pop(); if (lc[u]) q.push(lc[u]); if (rc[u]) q.push(rc[u]); } } cout ans \n; return 0; }我也测试过递归版本在本题的表现在不是极端链状数据的情况下确实没问题。但把“可能爆栈”的风险交给评测环境去决定不是我的风格。所以我的建议很简单第一遍做用递归体会逻辑第二遍做换成BFS体会空间差异第三遍再用手写栈体会显式栈的写法。三遍下来这道题的收益就被你榨干了。4.4 做模板题时最容易忽视的心态问题刷这种基础题最怕的是“看懂题解就觉得自己会了”。P4913的代码不算长但你如果只是在脑海里跑一遍递归过程或者直接抄一遍就交那其实没有真正内化。我自己的习惯是看完思路之后关掉题解自己从空文件开始写。写不出来再回头瞄一眼写出来之后再造两个极端数据跑一跑。这里的极端数据包括单节点、只有左孩子的一条链、满二叉树这三种形态。每种形态分别跑出答案再对照定义手算验证。这个过程大约多花十分钟但能让你的记忆深刻得多。另外提一个和做题无关但很实用的小建议如果你经常在洛谷上刷题可以留意一下题单的分类。像动态规划题单里有很多树形DP的题目它们的前置要求就是你能熟练写出树的深度信息统计也就是P4913这道题练的东西。别觉得基础题“太水”后面很多中等题卡住的恰恰不是高级算法而是这种“能不能干净利落地拿到子树信息”的基本功。我个人在实际操作中的体会是P4913最好的打开方式不是“求一个答案”而是把它当成一个可以反复重写的练手场景。递归写一遍BFS写一遍手写栈写一遍每次都能发现上一版代码里一些不够稳的地方。最后再分享一个小技巧每次做树题都先自己写一组“单点、链、满树”三个数据配合手算答案再提交。这个习惯帮我省下了无数次无谓的WA重交也让我后来面对新树的题目时心里更有底。