P3605. 生成哈夫曼树

解题思路

节点类的构建

普通的二叉树节点包括三个属性：值 val、左节点 left、右节点 right。 但本题构建哈夫曼树的过程还需要考虑到子树的高度，因此还需要储存一个 高度 属性 height。

构建哈夫曼树

本题的难点其实在于 如何构建哈夫曼树。

哈夫曼树的定义，用通俗易懂的话来理解就是：

• 值越小的叶节点需要离根部越远
• 值越大的叶节点需要离根部越近

满足上述定义的树就是哈夫曼树。 但为了保证构建出来的树是唯一的，以保证输出的二叉树中序遍历结果统一，题目还包含了如下描述： > 二叉树节点中，左节点权值小于等于右节点权值，根节点权值为左右节点权值之和。当左右节点权值相同时，左子树高度小于等于右子树。

这也要在后续的构建中考虑。

哈夫曼树通常用于各种数据压缩，譬如文件、图片、音频压缩，都会用到哈夫曼树。树上的节点值，在数据压缩中通常表示某些字符出现的次数。

具体例子

我们先看一个具体的例子。对于例子，我们可以从叶节点开始进行哈夫曼树的构建，其过程如下：

• 再重复上述过程
• 然后重复上述过程

构建树的逻辑

从上述例子可以窥见我们构建哈夫曼树的逻辑： 总是在剩余节点中，挑选出值最小的两个节点进行组合，来作为一个新节点的左右子节点。其中：

• 新节点的值为左右子节点值的和
• 如果两个子节点的值不同，则令数值更小的节点为左节点
• 如果两个子节点的值相同，则令高度更小的节点为左节点

节点数组初始化

最开始的时候，我们需要构建一个节点对象数组，其中包含了所有的叶节点。这些叶节点的左右节点均为 None，高度为 0。

这些叶节点会是构建哈夫曼树的基础。

只考虑节点值来构建树

我们需要在 node_lst 中挑选出两个值最小的节点，根据这两个节点来构建一个新节点 new_node。 由于需要挑选出值最小的两个节点，所以我们可以对 node_lst 进行排序。

新节点的值为这两个节点值的和，新节点的左节点为值较小的节点，新节点的右节点为值较大的节点。高度暂时先不考虑，设置为 0。

新节点需要重新加入 node_lst，在后续这个节点会继续作为树中的节点来构建树。

同时考虑节点高度来构建树

在只考虑节点值来构建树的过程中，我们默认了左节点的值是小于右节点的值的。 但题目中的描述存在这样一句话：当左右节点权值相同时，左子树高度小于等于右子树。 这意味着左节点的值可能等于右节点的值，且在相等的时候我们需要同时考虑两棵子树的高度。

所以我们在对 node_lst 进行排序的时候，要同时考虑每一个节点的高度。仍然优先按照节点值进行逆序排序，再按照高度进行逆序排序。修改代码：

而新节点的高度 height，等于弹出的两个左右节点的高度中的较大值再加 1，其中加 1 表示新节点带来的新增高度。

height 也要作为属性来构建 new_node。所以上述代码修改为：

在循环中构建树

上述的流程只是构建了一棵子树，我们需要重复上述过程，直到构建出一棵完整的哈夫曼树。 那么构建到什么程度说明哈夫曼树完全构建完毕了呢？答案是 当 `node_lst` 中只剩下一个节点的时候，那么这个剩下的唯一节点就是根节点。

因此整体的构建树的函数 build_tree() 如下：

中序遍历

构建完哈夫曼树之后，剩下的中序遍历就非常简单了。 在得到根节点 root = node_lst[0] 之后，直接套模板即可。

其他优化

上述解法已经可以通过全部用例了，但如果想实现更优的时间复杂度，排序并取节点的这一步，可以用 堆排序即优先队列 来代替。 这样可以将构建树中 while 循环中的单步操作的时间复杂度从 O(NlogN) 降为 O(logN)。