流利说编程题

想不到哈弗曼树居然写不出来啊啊啊啊啊
后来自己捋一捋，理清思路写出来了。。

import java.util.*;

public class EncodeString {

    static class HuffmanNode implements Comparable<HuffmanNode> {

        char value;

        int frequence;

        HuffmanNode left;

        HuffmanNode right;

        HuffmanNode(char value, int frequence) {
            this.value = value;
            this.frequence = frequence;
        }

        HuffmanNode(char value, int frequence, HuffmanNode left, HuffmanNode right) {
            this.value = value;
            this.frequence = frequence;
            this.left = left;
            this.right = right;
        }

        public int compareTo(HuffmanNode o) {
            return this.frequence - o.frequence;
        }

        public boolean isLeaf() {
            return left == null && right == null;
        }
    }

    public static String huffmanTree(String s) {
        int len = s.length();
        //根据明文先构建树，才可以压缩

        //计算频率
        HashMap<Character,Integer> frequences = new HashMap<>();
        char[] input = s.toCharArray();
        for (int i = 0; i < input.length; i++) {
            if (frequences.containsKey(input[i]))
                frequences.put(input[i],frequences.get(input[i]) + 1);
            else
                frequences.put(input[i],1);
        }

        PriorityQueue<HuffmanNode> pq = new PriorityQueue<>();//暂时保存子树
        //初始化多个树
        for (Character word: frequences.keySet()) {
            HuffmanNode node = new HuffmanNode(word, frequences.get(word));
            pq.add(node);
        }
        //开始创建
        while (pq.size() > 1) {
            HuffmanNode left = pq.poll();
            HuffmanNode right = pq.poll();
            HuffmanNode parent = new HuffmanNode('\0', left.frequence + right.frequence, left, right);
            pq.add(parent);
        }
        HuffmanNode root = pq.poll();

        //计算编码
        HashMap<Character,String> codes = new HashMap<>();
        initCodes(root, "",codes);

        return compress(input,codes);
    }

    public static String compress(char[] input,HashMap<Character,String> codes) {
        String output = "";
        for (int i = 0; i < input.length; i++) {
            String code = codes.get(input[i]);
            output += code;
        }
        return output;
    }

    private static void initCodes(HuffmanNode node, String s,HashMap<Character,String> map) {
        if (node.isLeaf()) {
            map.put(node.value,s);
            return;
        }
        initCodes(node.left, s + '0',map);
        initCodes(node.right, s + '1',map);
    }

    public static void main(String[] args) {
        System.out.println(huffmanTree("liulishuo").length());

    }

}