[Java] Trie + PostOrder + DFS
Three steps process:\n1. Construct a Trie-like structure. Using map for children node since path is a string, not just a single character.\n\n2. PostOrder - Not
Three steps process:\n1. Construct a Trie-like structure. Using map for children node since path is a string, not just a single character.\n\n2. PostOrder - Note it down. For duplication detection in tree, postOrder is the key to get substructure. \n\ta. The substructure can be encoded any way you want. The easiest one is to use \'(\' and \')\' to denote levels. a (b, c,d (...),) (Note: my solution has an ending \',\' in the children list but not really matter.)\n\tb. The important here is the order of node\'s children. For example \'a(b,c)\' vs \'a(c,b)\'. Use TreeMap for node.children to work around it. \n\tc. Record substructure int a map<String, Node> with key is a serialized structure string.\n\tc. Mark the node.dup = true if its substructure has seen earlier. \n\n3. DFS and stop at nodes which node.dup=true.\n\n\n```\nclass Solution {\n    Node root = new Node("*");\n    Map<String, Node> map= new HashMap<>();\n    public List<List<String>> deleteDuplicateFolder(List<List<String>> paths) {\n        constructTrie(paths);\n        postOrder(root);\n        List<List<String>> res = new ArrayList<>();\n        dfs(res, root, new ArrayList<String>());\n        return res;\n    }\n    \n    public String postOrder(Node node) {\n        StringBuffer s = new StringBuffer();\n        for (Node cn : node.children.values()) {\n            s.append(postOrder(cn));\n            s.append(",");\n        }\n\n        String key = s.toString();\n        if (s.length() == 0) return node.val + key; // leaf node\n        if (map.containsKey(key)) {\n            Node orig = map.get(key);\n            orig.dup = true;\n            node.dup = true;\n        } else {\n            map.put(key, node);\n        }\n        \n        return node.val + "(" + key + ")";\n    }\n    \n    public void dfs(List<List<String>> res, Node node, List<String> str) {\n        if (node == null) return;\n        for(Node cn : node.children.values()) {\n            if (cn.dup) continue;\n            str.add(cn.val);\n            List<String> result = new ArrayList<>();\n            result.addAll(str);\n            res.add(result);\n            dfs(res, cn, str);\n            str.remove(str.size()-1);\n        }\n    }\n    \n    public void constructTrie(List<List<String>> paths) {\n        for (List<String> path : paths) {\n            Node cur  = root;\n            for (String ss : path) {\n                cur = cur.children.computeIfAbsent(ss, s -> new Node(s));\n            }\n        }\n    }\n}\n\nclass Node {\n    Map<String, Node> children;\n    String val;\n    boolean dup;\n    public Node(String val) {\n        children = new TreeMap<String, Node>();\n        this.val = val;\n        dup = false;\n    }\n}\n\n```
[]