生成哈夫曼树
题目描述
给定长度为 n nn 的无序的数字数组, 每个数字代表二叉树的叶子节点的权值, 数字数组的值均大于等于 1 11. 请完成一个函数, 根据输入的数字数组, 生成哈夫曼树, 并将哈夫曼树按照中序遍历输出.
为了保证输出的二叉树中序遍历结果统一, 增加以下限制:又树节点中, 左节点权值小于等于右节点权值, 根节点权值为左右节点权值之和. 当左右节点权值相同时, 左子树高度高度小于等于右子树.
注意: 所有用例保证有效, 并能生成哈夫曼树提醒:哈夫曼树又称最优二叉树, 是一种带权路径长度最短的一叉树.
所谓树的带权路径长度, 就是树中所有的叶结点的权值乘上其到根结点的路径长度 (若根结点为 0 00层, 叶结点到根结点的路径长度为叶结点的层数).
输入描述
例如: 由叶子节点 5 15 40 30 10 生成的最优二叉树如下图所示, 该树的最短带权路径长度为 40 * 1 + 30 * 2 +5 * 4 + 10 * 4 = 205
输出描述
输出一个哈夫曼的中序遍历数组, 数值间以空格分隔.
示例1
输入:
5
5 15 40 30 10
输出:
40 100 30 60 15 30 5 15 10