C++ Tree building and trimming
See my latest update in repo LeetCode\n\n## Solution 1. DFS\n\n1. Build Tree: Build a folder tree based on the paths. The process is similar to the Trie buildin
See my latest update in repo [LeetCode](https://github.com/lzl124631x/LeetCode)\n\n## Solution 1. DFS\n\n1. **Build Tree**: Build a folder tree based on the `paths`. The process is similar to the Trie building process.\n2. **Dedupe**: Use post-order traversal to visit all the nodes. If we\'ve seen the subfolder structure before, mark the node as deleted.\n3. **Generate Paths**: DFS to generate the output. We skip the nodes that have been deleted.\n\nUpdate 1: To ensure we visit the subfolders in the same order, changed `Node::next` to `unordered_map` to `map`. (Testcase: `[["a"],["a","a"],["a","b"],["a","b","a"],["b"],["b","a"],["b","a","a"],["b","b"]]`. Thanks @wshack)\n\nUpdate 2: To ensure the subfolder structure string only map to a unique tree structure, changed the encoding to use parenthesis instead, e.g. `(root(firstChild)(secondChild)...)`. (Testcase: `[["r","x"],["r","x", "b"],["r","x","b","a"],["r", "y"],["r","y", "a"],["r","y", "b"],["r"]]`. Thanks @Asagi)\n\n**Complexity Analysis**\n\nAssume `N` is the number of folders, `W` is the maximum length of folder name, `D` is the deepest folder depth, and `C` is the maximum number of direct **c**hild folders.\n\n1. **Build Tree**: We need to add all the `N` folders, each of which takes `O(DWlogC)` time. So overall it takes `O(NDWlogC)` time, and `O(NW)` space.\n2. **Dedupe**: We traverse the `N` folders in post-order. The maximum length of `subfolder` structure string is roughly `O(NW)`, so each node visit need `O(NW)` time to check if it\'s a duplicate. The overall time complexity is `O(N^2 * W)` and the space complexity is `O(N^2 * W)`.\n3. **Generate Paths**: In the worst case we traverse the `N` nodes again. Each visit takes `O(W)` time to update the current `path` and `O(DW)` time to update the answer. So overall the time complexity is `O(NDW)` and space complexity is `O(DW)` for the temporary `path`.\n\n```cpp\n// OJ: https://leetcode.com/contest/weekly-contest-251/problems/delete-duplicate-folders-in-system/\n// Author: github.com/lzl124631x\n// Time: O(NDWlogC + N^2 * W) where `N` is the number of folders, `W` is the maximum length of folder name, \n//                                  `D` is the deepest folder depth, and `C` is the maximum number of direct child folders.\n// Space: O(N^2 * W)\nstruct Node {\n    string name;\n    map<string, Node*> next; // mapping from folder name to the corresponding child node.\n    bool del = false; // whether this folder is deleted.\n    Node(string n = "") : name(n) {}\n};\nclass Solution {\n    void addPath(Node *node, vector<string> &path) { // Given a path, add nodes to the folder tree. This is similar to the Trie build process.\n        for (auto &s : path) {\n            if (node->next.count(s) == 0) node->next[s] = new Node(s);\n            node = node->next[s];\n        }\n    }\n    unordered_map<string, Node*> seen; // mapping from subfolder structure string to the first occurrence node.\n    string dedupe(Node *node) { // post-order traversal to dedupe. If we\'ve seen the subfolder structure before, mark it as deleted.\n        string subfolder;\n        for (auto &[name, next] : node->next) {\n            subfolder += dedupe(next);\n        }\n        if (subfolder.size()) { // leaf nodes should be ignored\n            if (seen.count(subfolder)) { // if we\'ve seen this subfolder structure before, mark them as deleted.\n                seen[subfolder]->del = node->del = true;\n            } else {\n                seen[subfolder] = node; // otherwise, add the mapping\n            }\n        }\n        return "(" + node->name + subfolder + ")"; // return the folder structure string of this node.\n    }\n    vector<vector<string>> ans;\n    vector<string> path;\n    void getPath(Node *node) {\n        if (node->del) return; // if the current node is deleted, skip it.\n        path.push_back(node->name);\n        ans.push_back(path);\n        for (auto &[name, next] : node->next) {\n            getPath(next);\n        }\n        path.pop_back();\n    }\npublic:\n    vector<vector<string>> deleteDuplicateFolder(vector<vector<string>>& A) {\n        Node root;\n        for (auto &path : A) addPath(&root, path);\n        dedupe(&root);\n        for (auto &[name, next] : root.next) getPath(next);\n        return ans;\n    }\n};\n```
[]