设计内存文件系统：在Trie中用TreeMap维护子节点

摘要: TreeMap 维护子节点的 Trie

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

在 Trie 中，一般用数组或哈希表维护子节点，本文我们看一个用TreeMap维护子节点的例子。

题目

588. 设计内存文件系统

设计一个内存文件系统，模拟以下功能：

实现文件系统类:

• FileSystem() 初始化系统对象
• List ls(String path)
  • 如果 path 是一个文件路径，则返回一个仅包含该文件名称的列表。
  • 如果 path 是一个目录路径，则返回该目录中文件和 目录名 的列表。答案应该 按字典顺序 排列。
• void mkdir(String path) 根据给定的路径创建一个新目录。给定的目录路径不存在。如果路径中的中间目录不存在，您也应该创建它们。
• void addContentToFile(String filePath, String content)
  • 如果 filePath 不存在，则创建包含给定内容 content的文件。
  • 如果 filePath 已经存在，将给定的内容 content附加到原始内容。
• String readContentFromFile(String filePath) 返回 filePath下的文件内容。

注意:

1 <= path.length, filePath.length <= 100
path 和 filePath 都是绝对路径，除非是根目录 ‘/’ 自身，其他路径都是以 ‘/’ 开头且 不 以 ‘/’ 结束。
你可以假定所有操作的参数都是有效的，即用户不会获取不存在文件的内容，或者获取不存在文件夹和文件的列表。
你可以假定所有文件夹名字和文件名字都只包含小写字母，且同一文件夹下不会有相同名字的文件夹或文件。
1 <= content.length <= 50
ls, mkdir, addContentToFile, and readContentFromFile 最多被调用 300 次

示例 1:

输入:
[“FileSystem”,”ls”,”mkdir”,”addContentToFile”,”ls”,”readContentFromFile”]
[[],[“/“],[“/a/b/c”],[“/a/b/c/d”,”hello”],[“/“],[“/a/b/c/d”]]
输出:
[null,[],null,null,[“a”],”hello”]

解释:
FileSystem fileSystem = new FileSystem();
fileSystem.ls(“/“); // 返回 []
fileSystem.mkdir(“/a/b/c”);
fileSystem.addContentToFile(“/a/b/c/d”, “hello”);
fileSystem.ls(“/“); // 返回 [“a”]
fileSystem.readContentFromFile(“/a/b/c/d”); // 返回 “hello”

题解

算法：Trie + TreeMap

内存文件系统中，文件路径由目录结构在组织，文件路径对应一个文件内容。文件内容可以添加或读取。文件夹也可以创建和读取。添加文件内容的时候，文件路径如果不存在，则创建。

整体思路是用 Trie 维护目录结构，Trie 中的一条路径对应一个文件路径。在 Trie 节点中记录文件或文件夹名，标记该路径是文件夹还是文件：

• 如果是文件夹，则会有若干子节点，子节点可能是文件也可能是文件夹。由于读取文件夹的时候需要有序输出，因此用平衡树维护子节点。
• 如果是文件，则在一个 string 变量中记录文件内容。对文件内容的添加和读取，都通过操作该变量实现。

代码 (C++)

struct Node
{
    bool fold;
    string content; // fold 为 false 时有意义
    string name;
    map<string, Node*> children; // fold 为 true 时有意义
    Node(bool fold, string name=""):fold(fold),name(name){}
};

class FileSystem {
public:
    FileSystem() {
        root = new Node(true);
    }

    vector<string> ls(string path) {
        auto it = _find(path);
        vector<string> result;
        if(it -> fold)
            for(auto item: it -> children)
                result.push_back(item.first);
        else
            result.push_back(it -> name);
        return result;
    }

    void mkdir(string path) {
        _find(path);
    }

    void addContentToFile(string filePath, string content) {
        auto it = _find(filePath);
        if(it -> fold == true) // 首次创建
            it -> fold = false;
        it -> content += content;
    }

    string readContentFromFile(string filePath) {
        auto it = _find(filePath);
        return it -> content;
    }

private:
    Node *root;

    Node* _find(const string& path)
    {
        Node *iter = root;
        int i = 0;
        int n = path.size();
        while(i + 1 < n)
        {
            int j = i + 1;
            while(j < n && path[j] != '/')
                ++j;
            string s = path.substr(i + 1, j - (i + 1));
            if(!(iter -> children)[s])
                (iter -> children)[s] = new Node(true, s);
            iter = (iter -> children)[s];
            i = j;
        }
        return iter;
    }
};

---