【题目来源】
洛谷：P4913 【深基16.例3】二叉树深度 - 洛谷
【题目描述】
有一个 \(n(n \le 10^6)\) 个结点的二叉树。给出每个结点的两个子结点编号（均不超过 \(n\)），建立一棵二叉树（根节点的编号为 \(1\)），如果是叶子结点，则输入 0 0。
建好这棵二叉树之后，请求出它的深度。二叉树的深度是指从根节点到叶子结点时，最多经过了几层。
【输入】
第一行一个整数 \(n\)，表示结点数。
之后 \(n\) 行，第 \(i\) 行两个整数 \(l\)、\(r\)，分别表示结点 \(i\) 的左右子结点编号。若 \(l=0\) 则表示无左子结点，\(r=0\) 同理。
【输出】
一个整数，表示最大结点深度。
【输入样例】
7
2 7
3 6
4 5
0 0
0 0
0 0
0 0
【输出样例】
4
【算法标签】
《洛谷 P4913 二叉树深度》 #搜索# #广度优先搜索BFS# #深度优先搜索DFS#
【代码详解】
#include <bits/stdc++.h>
using namespace std;const int N = 1e6 + 5; // 二叉树最大节点数
string str; // 未使用的字符串变量// 二叉树节点结构体
struct tree
{int name; // 节点名称（实际上等于数组下标）int lchild; // 左子节点下标int rchild; // 右子节点下标
}trees[N]; // 二叉树数组int n, ans; // n: 节点数量，ans: 树的最大深度// 深度优先搜索计算树的最大深度
void dfs(int root, int dep) // root: 当前子树根节点下标，dep: 当前深度
{if (root == 0) // 空节点，返回{return;}ans = max(ans, dep); // 更新最大深度// 递归遍历左子树dfs(trees[root].lchild, dep + 1);// 递归遍历右子树dfs(trees[root].rchild, dep + 1);
}int main()
{cin >> n; // 读入节点数量// 读入每个节点的左右子节点for (int i = 1; i <= n; i++){trees[i].name = i; // 设置节点名称cin >> trees[i].lchild; // 读入节点i的左子节点下标cin >> trees[i].rchild; // 读入节点i的右子节点下标}dfs(1, 1); // 从1号节点开始深度优先搜索，根节点深度为1cout << ans << endl; // 输出树的最大深度return 0;
}
【运行结果】
7
2 7
3 6
4 5
0 0
0 0
0 0
0 0
4