[题目描述]

给你一棵字典树，设计一种序列化的方式，并且同时要能够设计对应的展开方法。

在线评测地址:

https://www.lintcode.com/problem/trie-serialization/?utm_source=sc-v2ex-fks

Example 1

Input: <a<b<e<>>c<>d<f<>>>> Output: <a<b<e<>>c<>d<f<>>>> Explanation: The trie is look like this.      root       /      a    / |    b  c  d  /        e         f 

Example 2

Input: <a<>> Output: <a<>> 

[题解]

class Solution {     /**      * This method will be invoked first, you should design your own algorithm       * to serialize a trie which denote by a root node to a string which      * can be easily deserialized by your own "deserialize" method later.      */     public String serialize(TrieNode root) {         // Write your code here         if (root == null)             return "";          StringBuffer sb = new StringBuffer();         sb.append("<");         Iterator iter = root.children.entrySet().iterator();          while (iter.hasNext()) {             Map.Entry entry = (Map.Entry)iter.next();              Character key = (Character)entry.getKey();              TrieNode child = (TrieNode)entry.getValue();             sb.append(key);             sb.append(serialize(child));         }         sb.append(">");         return sb.toString();     }      /**      * This method will be invoked second, the argument data is what exactly      * you serialized at method "serialize", that means the data is not given by      * system, it's given by your own serialize method. So the format of data is      * designed by yourself, and deserialize it here as you serialize it in       * "serialize" method.      */     public TrieNode deserialize(String data) {         // Write your code here         if (data == null || data.length() == 0)             return null;          TrieNode root = new TrieNode();         TrieNode current = root;         Stack<TrieNode> path = new Stack<TrieNode>();         for (Character c : data.toCharArray()) {             switch (c) {             case '<':                 path.push(current);                 break;             case '>':                 path.pop();                 break;             default:                 current = new TrieNode();                 path.peek().children.put(c, current);             }         }         return root;     } 

[更多语言代码参考]

https://www.jiuzhang.com/solution/trie-serialization/?utm_source=sc-v2ex-fks

大佬有話說 (0)