import java.util.TreeMap;

class MapSum {

    /**
     * 本题中每个节点还有一个对应的val，可以替代isWord的作用
     */
    class Node{

        int val;
        TreeMap<Character, Node> next;

        public Node(int val){

            this.val = val;
            next = new TreeMap<>();
        }

        public Node(){

            this(0);
        }
    }

    Node root;

    public MapSum() {

        root = new Node(0);
    }

    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.val = 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);
    }

    /**
     * 根据某个节点遍历所有的子路径
     */
    public int sum(Node root){

        int res = root.val;

        for (char c : root.next.keySet()){
            res += sum(root.next.get(c));
        }

        return res;
    }
}

https://leetcode-cn.com/problems/map-sum-pairs/