LeetCode677. 键值映射（相关话题：Trie前缀树）

分析：在这个案例中，Trie是作为一种映射来使用（在Node节点中存储了一个value值）。

集合和映射的关系：映射本身就是把集合中的每一个元素当做一个键，每一键绑定一个value，绑定体现在Node中。

import java.util.TreeMap;
class MapSum {

    private class Node{
        public int value;
        public TreeMap<Character, Node> next;
        public Node(int value){
            this.value = value;
            next = new TreeMap<>();
        }
        public Node(){
            this(0);
        }
    }
    private Node root;
    /** Initialize your data structure here. */
    public MapSum() {
        root = new Node();

    }
    
    public void insert(String key, int val) {
        Node cur = root;
        for(int i = 0; i < key.length(); i++){
            char c = key.charAt(i);
            if(cur.next.get(c) == null){
                cur.next.put(c, new Node());
            }
            cur = cur.next.get(c);
        }
        cur.value = val;
    }
    
    public int sum(String prefix) {
        Node cur = root;
        for(int i = 0; i < prefix.length(); i++){
            char c = prefix.charAt(i);
            if(cur.next.get(c) == null){
                return 0;
            }
            cur = cur.next.get(c);
        }
        return sum(cur); // 以cur作为根结点进行遍历
    }
    // 遍历node以及node所有的子树，将所有节点的value值加起来。
    private int sum(Node node){
        // 显示指出（可以注释掉）递归到底的情况——当前节点是叶子节点，即下一个节点的映射大小为0，也就是没有下一个节点
        // if(node.next.size() == 0){
        //     return node.value;
        // }
        int res = node.value;
        // node可以指向的所有下一个字符相应的节点   (如果是叶子节点循环的遍历不会执行，相当于直接return node.value)
        for(char c : node.next.keySet()){
            res += sum(node.next.get(c)); //递归，以这个节点为根的sum值
        }
        return res;
    }
}

/**
 * Your MapSum object will be instantiated and called as such:
 * MapSum obj = new MapSum();
 * obj.insert(key,val);
 * int param_2 = obj.sum(prefix);
 */