DFS traversal and encode tree's values and tree's structure
\n class Solution {\n    \n    class Trie {\n        \n        int val;\n        Map<Integer, Trie> next; \n        String encoded;\n        boolean isDeleted;\
```\n class Solution {\n    \n    class Trie {\n        \n        int val;\n        Map<Integer, Trie> next; \n        String encoded;\n        boolean isDeleted;\n        \n        Trie(int val) {\n            this.val = val;\n            this.next = new HashMap<Integer, Trie>();\n            this.encoded = "";\n            this.isDeleted = false;\n        }\n    }\n    \n    public String dfsToEncode(Trie root, Map<String, Trie> treeMap) {\n        \n        for(Integer key : root.next.keySet()) {\n            root.encoded = (root.encoded.length() > 0) ? root.encoded + \',\' + dfsToEncode(root.next.get(key), treeMap) : dfsToEncode(root.next.get(key), treeMap);\n        }\n        \n        if (root.encoded.length() > 0) {\n            if (!treeMap.containsKey(root.encoded)) {\n                treeMap.put(root.encoded, root);    \n            } else {\n                root.isDeleted = true;\n                treeMap.get(root.encoded).isDeleted = true;\n            }\n        \n            if (root.encoded.length() == 0) {\n                return String.valueOf(root.val);\n            } \n        }\n        \n        return String.valueOf(root.val) + "," + root.encoded;\n    }\n    \n    public static List<String> clone(List<String> list) {\n        \n        List<String> clonedList = new ArrayList<String>();\n        \n        for(String s : list) {\n            clonedList.add(s);\n        }\n        \n        return clonedList;\n    }\n    \n    public void dfs(Trie root, Map<Integer, String> intToFolder, List<List<String>> ans, List<String> pre) {\n        \n        if (!root.isDeleted) {\n            \n            List<String> cur =  clone(pre);\n            \n            if (root.val != -1) {\n               cur.add(intToFolder.get(root.val));\n               ans.add(cur);\n            }\n            \n            for(Integer key : root.next.keySet()) {\n                // System.out.println(key + " " + intToFolder.get(root.val));\n                dfs(root.next.get(key), intToFolder, ans, cur);\n            }\n        }\n    }\n    \n    public List<List<String>> deleteDuplicateFolder(List<List<String>> paths) {\n        \n        Map<String, Integer> folderToInt = new HashMap<String, Integer>();\n        Map<Integer, String> intToFolder = new HashMap<Integer, String>();\n        \n        int cnt = 0;\n        \n        Trie root = new Trie(-1);\n        for(List<String> path : paths) {\n            Trie cur = root;\n            for(String folder : path) {\n                \n                if (!folderToInt.containsKey(folder)) {\n                    folderToInt.put(folder, cnt);\n                    intToFolder.put(cnt, folder);\n                    cnt++;\n                }\n                \n                int num = folderToInt.get(folder);\n                \n                if (!cur.next.containsKey(num)) {\n                    cur.next.put(num, new Trie(num));\n                }\n                cur = cur.next.get(num);\n            }\n        }\n        \n        Map<String, Trie> treeMap = new HashMap<String, Trie>();\n        dfsToEncode(root, treeMap);\n        \n        List<List<String>> ans = new ArrayList<List<String>>();\n        dfs(root, intToFolder, ans, new ArrayList<String>());\n        \n        return ans;\n    }\n}\n```
[]