Java | Concise | Briefly Explained + Comments
I tried to hash the tree with long but there were hash collision, so I changed it to String.\n\nBasically 3 steps:\n1. Create the tree. It is similar to how one
I tried to hash the tree with long but there were hash collision, so I changed it to String.\n\nBasically 3 steps:\n1. Create the tree. It is similar to how one would build a Trie\n2. Hash The Tree with **Post-Order** DFS traversal & mark duplicate subtrees. This is linear time. \n3. DFS again to add all paths that aren\'t marked deleted.\n\nI used a TreeMap to maintain children\'s order.\n#### Java\n```Java\n// 173ms (77% Speed)\n// 69.8 MB (92% Memory)\nclass Solution {\n    public List<List<String>> deleteDuplicateFolder(List<List<String>> paths) {\n        List<List<String>> ans = new ArrayList<>();\n        Tree root = new Tree();\n        for (List<String> p : paths){ // build the tree\n            Tree cur = root;\n            for (String f : p){\n                cur.sub.putIfAbsent(f, new Tree());\n                cur = cur.sub.get(f);\n                cur.name = f;\n            }\n        }\n        mark(root, new HashMap<>()); // hash + mark\n        populate(root, new ArrayList<>(), ans); // populate all paths\n        return ans;\n    }\n\n    private String mark(Tree root, Map<String, Tree> seen){\n        StringBuilder sb = new StringBuilder("T"); // Start\n        for (String key : root.sub.keySet()){\n            Tree next = root.sub.get(key);\n            sb.append(mark(next, seen)).append("S"); // children separator \n        }\n        if (seen.containsKey(sb.toString())){ // delete duplicates\n            root.deleted=seen.get(sb.toString()).deleted=true;\n        }\n        if (!root.sub.isEmpty()){ // Leaf node doesn\'t get to compare\n            seen.put(sb.toString(), root);\n        }\n        sb.append("P").append(root.name); // Add itself\n        return sb.toString();\n    }\n\n    private void populate(Tree root, List<String> tmp, List<List<String>> ans){\n        if (root.deleted){\n            return;\n        }\n        if (!root.name.isEmpty()){ // add current path\n            tmp.add(root.name);\n            ans.add(new ArrayList<>(tmp));\n        }\n        for (String key : root.sub.keySet()){ // recursively add all subpaths \n            populate(root.sub.get(key), tmp, ans);\n        }\n        if (!tmp.isEmpty()){\n            tmp.remove(tmp.size()-1);\n        }\n    }\n\n    private class Tree {\n        boolean deleted;\n        String name = "";\n        Map<String, Tree> sub = new TreeMap<>();\n        Tree(){}\n    }\n}\n```
['Java']