[力扣/领扣算法题解] 序列化 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) {
        // 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