disk tree题解

题目描述：

给定一些文件夹和文件，要求将它们按照层级关系输出成一个树形结构。

输入格式：

输入的第一行包含一个整数 n，表示文件夹和文件的个数。

接下来 n 行，每行包含一个字符串，表示一个文件夹或者文件。

其中，文件名和文件夹名都不包含空格和斜杠，文件名包含一个小数点，表示文件后缀。

输出格式：

输出一个树形结构，每行表示一个文件夹或者文件，按照层级关系缩进，文件夹名称后面要加上一个斜杠。

注意，最后一个文件夹或者文件名称后面不能有空格。

样例：

输入：

6
/root
/etc
/root/abcd.txt
/root/bcd/
/etc/test/
/root/bcd/efg.txt

输出：

/root
/abcd.txt
/bcd/
/efg.txt
/etc
/test/

算法1

(模拟) $O(n)$

思路：

本题需要我们输出文件夹和文件的层级结构，因此可以考虑使用哈希表记录每个文件夹和文件的层级结构。

对于每个文件夹和文件，我们可以通过判断其路径中"/"的数量来确定其所在的层级结构，具体来说，每个"/"表示一层。因此，我们可以将路径按"/"分开，然后统计"/"的数量，就可以得到该文件夹或文件所在的层级结构。

同时，由于本题要求输出树形结构，因此我们需要对每个文件夹和文件进行缩进处理，使其在输出时具有层级关系。具体来说，我们可以通过其所在的层级结构来确定输出时需要添加的缩进空格数量。

最后，我们可以按照文件夹和文件的层级结构从小到大的顺序进行输出，这样能够保证每个文件夹和文件的父节点已经被输出过了。

时间复杂度

哈希表的查询和插入操作都是常数级别的，因此总时间复杂度为 $O(n)$。

C++ 代码

算法2

(模拟) $O(nlogn)$

思路：

本题可以使用字典树来实现，具体来说，我们可以将每个文件夹和文件的路径看作一个字符串，然后将所有字符串插入到字典树中。

同时，我们可以定义一个结构体，用来存储每个字符串的层级结构和缩进空格数量，具体来说，每个字符串的层级结构可以通过其在字典树中的深度来确定，而每个字符串的缩进空格数量则可以通过其所在的层级结构来确定。

最后，我们可以按照字符串的层级结构从小到大的顺序进行输出，这样能够保证每个字符串的父节点已经被输出过了。

时间复杂度

插入字符串的时间复杂度为 $O(nlogn)$，输出字符串的时间复杂度也为 $O(nlogn)$，因此总时间复杂度为 $O(nlogn)$。

C++ 代码