题目内容

现有一棵$n$个节点构成的哈夫曼树，哈夫曼树的定义如下: 1.每个节点要么没有父节点连接(此时该节点被称为根节点$^1$)、要么被$1$个父节点连接(此时该节点被称为父节点的子节点$^2$); 2.每个节点连接的子节点$^2$数量要么为$0$(此时该节点被称为“叶子节点$^3$”)、要么小于等于$2$;

3.如果存在子节点$^2$，节点权值为左右子节点$^2$的权值之和，且左子节点$^2$权值小于等于右子节点$^2$;

4.哈夫曼树的所有节点权值之和尽可能小，即权值越小的叶子节点$^3$在树中的位置越靠下;