题目描述
有一个 n(n≤10^6) 个结点的二叉树。给出每个结点的两个子结点编号（均不超过 n），建立一棵二叉树（根节点的编号为 1），如果是叶子结点，则输入0 0。
建好这棵二叉树之后，请求出它的深度。二叉树的深度是指从根节点到叶子结点时，最多经过了几层。
输入格式
第一行一个整数 n，表示结点数。
之后 n 行，第 i 行两个整数 l、r，分别表示结点 i 的左右子结点编号。若 l=0 则表示无左子结点，r=0 同理。
输出格式
一个整数，表示最大结点深度。
输入输出样例
输入 #1复制
7 2 7 3 6 4 5 0 0 0 0 0 0 0 0
输出 #1复制
4
问题分析与核心思路
本题要求计算给定二叉树的最大深度。我们采用广度优先搜索 (BFS)来解决，因为它天然地按层级遍历。
BFS 特性：保证先访问层级低的节点，后访问层级高的节点。
深度计算：在遍历过程中，利用父节点的深度信息，推算出子节点的深度（父节点深度+ 1）。
最终答案：所有节点中记录的最大层级值即为树的最大深度。
📊 数据结构设计
为了存储树结构和节点深度，我们定义了结构体node：
struct node{ int l;//左儿子 int r;//右儿子 int level;//节点所在层级/深度 }a[1000001];a数组存储所有节点信息。queue<node> q用于辅助 BFS 遍历。ma记录当前已知的最大深度。
BFS 算法实现 (bfs函数)
bfs函数实现了核心的层序遍历逻辑。
1. 初始化
将根节点（编号 1）入队，并假设其深度已初始化为 1。
2. 循环遍历
使用while(!q.empty())进行循环。
出队访问：
node tmp=q.front(); q.pop();处理左儿子：
if(tmp.l!=0){ // 检查左儿子是否存在 // 关键：a[i].level == 0 标记节点是否已访问 if(a[tmp.l].level==0){ a[tmp.l].level=tmp.level+1; // 新深度 = 父节点深度 + 1 q.push(a[tmp.l]); // 左儿子入队 ma=max(ma,a[tmp.l].level); // 更新最大深度 } }处理右儿子：
处理逻辑与左儿子相同，确保右儿子也入队并更新最大深度。
3. 结果输出
遍历完成后，输出ma。
完整代码流程
在main函数中，我们负责读取数据、初始化根节点深度，并调用 BFS 函数。
//洛谷P4913 【深基16.例3】二叉树深度 #include <iostream> #include <queue> using namespace std; struct node{ int l;//左儿子 int r;//右儿子 int level;//节点所在层次 }a[1000001]; int ma=0; queue<node> q; void bfs(int root){//根节点传进来 node tmp; tmp=a[root]; q.push(tmp);//根节点入队 while(!q.empty()){ tmp=q.front();//访问队首元素 q.pop();//队首出队 //得有左儿子 if(tmp.l!=0) { //左儿子没有走过 if(a[tmp.l].level==0){ a[tmp.l].level=tmp.level+1; q.push(a[tmp.l]);//没有访问过就入队 ma=max(ma,a[tmp.l].level); } } //得有右儿子 if(tmp.r!=0){ //右儿子没有走过 if(a[tmp.r].level==0){ a[tmp.r].level=tmp.level+1; q.push(a[tmp.r]); ma=max(ma,a[tmp.r].level); } } } cout<<ma; } int main(){ int n; cin>>n; for(int i=1;i<=n;i++) cin>>a[i].l>>a[i].r; a[1].level=1; ma=1; bfs(1); return 0; }