# [力扣/领扣算法题解] 序列化 Trie · Trie Serialization

[题目描述]

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) {
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) {
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

Click to rate this post!
[Total: 0 Average: 0]