[Python] Trie & Serialize subtrees - Clean & Concise
Idea\n- Use TrieNode to create the graph of folder structure.\n- Then dfs on our graph and serialize subtrees as strings, then add nodes which has the same seri
**Idea**\n- Use `TrieNode` to create the graph of folder structure.\n- Then dfs on our graph and serialize subtrees as strings, then add nodes which has the same serialize string into a dictionary, let name it `seen`.\n- Traverse the `seen` dictionary, if nodes has the same serialize string, then it\'s duplicated subtree, we mark those nodes as `deleted`.\n- Traverse the whole graph again, if the node is not deleted, we add the paths to our result `ans`.\n\n```python\nclass TrieNode:\n    def __init__(self):\n        self.child = defaultdict(TrieNode)\n        self.deleted = False\n    def addWord(self, word):\n        curr = self\n        for c in word: curr = curr.child[c]\n\nclass Solution:\n    def deleteDuplicateFolder(self, paths: List[List[str]]) -> List[List[str]]:\n        def serialize(root, seen):\n            if not root.child: return ""\n            keys = []\n            for c, child in root.child.items():\n                keys.append(c + ":" + serialize(child, seen))\n            key = "(" + "".join(keys) + ")"\n            seen[key].append(root)\n            return key\n\n        def dfsGetValidPaths(root, path, out):\n            for c, child in root.child.items():\n                if not child.deleted:\n                    out.append(path + [c])\n                    dfsGetValidPaths(child, path + [c], out)\n\n        trieRoot, seen = TrieNode(), defaultdict(list)\n        # Create graph\n        for path in sorted(paths):  # Sort paths to get correct orders of children of a subtree\n            trieRoot.addWord(path)\n\n        # Find duplicated subtrees\n        serialize(trieRoot, seen)\n\n        # Mark duplicated subtree nodes as deleted\n        for nodes in seen.values():\n            if len(nodes) >= 2:\n                for node in nodes:  # Mark duplicated subtrees as deleted\n                    node.deleted = True\n\n        ans = []\n        dfsGetValidPaths(trieRoot, [], ans)\n        return ans\n```
[]