练习 13：树的深度（入门）

题目描述：

给定一棵以 1 为根的有根树，有 n 个结点。求这棵树的最大深度（根结点的深度定义为 1）。

输入格式：

• 第一行：一个正整数 n（2 ≤ n ≤ 1000）
• 第二行：n-1 个正整数 f_2, f_3, ..., f_n，其中 f_i 表示结点 i 的父结点编号

输出格式：

• 一行，一个整数，表示树的最大深度

样例输入：

5
1 1 2 2

样例输出：

3

样例解释：

树的结构：

    1
   / \
  2   3
 / \
4   5

• 根结点 1 的深度为 1
• 结点 2, 3 的深度为 2
• 结点 4, 5 的深度为 3

最大深度为 3。

提示：

• 方法1：DFS 递归

  • dfs(u, depth) 表示当前访问结点 u，深度为 depth
  • 遍历所有子结点时，传入 depth + 1
  • 用全局变量 maxDepth 记录最大深度

• 方法2：BFS 层序遍历

  • 用队列按层遍历，每遍历完一层，深度 +1
  • 记录遍历了多少层