Python 实现计算从 n 号文件夹追溯到根目录的层数，附代码详解与复杂度分析

以下是使用 Python 实现的代码： ```python # 读取文件夹总数 n = int(input()) # 初始化一个列表来存储每个文件夹的父目录 parent = [0] * (n + 1) # 读取每个文件夹的父目录信息 for i in range(2, n + 1): parent[i] = int(input()) # 初始化层数为 0 layers = 0 # 从 n 号文件夹开始 current_folder = n # 不断向上访问父目录，直到到达根目录（1 号文件夹） while current_folder != 1: # 访问父目录 current_folder = parent[current_folder] # 层数加 1 layers += 1 # 输出结果 print(layers) ``` 代码解释： 1. 读取文件夹总数：使用 `input()` 函数读取用户输入的文件夹总数 `n`，并将其转换为整数类型。 2. 初始化父目录列表：创建一个长度为 `n + 1` 的列表 `parent`，用于存储每个文件夹的父目录编号。索引 `i` 表示文件夹的编号，`parent[i]` 表示该文件夹的父目录编号。 3. 读取父目录信息：使用 `for` 循环从 2 到 `n` 读取每个文件夹的父目录编号，并将其存储在 `parent` 列表中。 4. 初始化层数：将层数 `layers` 初始化为 0。 5. 从 `n` 号文件夹开始追溯：将当前文件夹 `current_folder` 初始化为 `n`，并使用 `while` 循环不断向上访问父目录，直到到达根目录（1 号文件夹）。 6. 访问父目录并增加层数：在每次循环中，将当前文件夹更新为其父目录，并将层数加 1。 7. 输出结果：当到达根目录时，循环结束，输出层数 `layers`。 复杂度分析： - 时间复杂度：$O(n)$，其中 $n$ 是文件夹的总数。在最坏情况下，需要访问每个文件夹一次。 - 空间复杂度：$O(n)$，主要用于存储每个文件夹的父目录编号。 ######[AI问答 | 506点数解答 | 2025-11-15 20:41:03]