題目描述

給定長度為 n 的無序的數字數組，每個數字代表二叉樹的葉子節點的權值，數字數組的值均大于等于1。

請完成一個函數，根據輸入的數字數組，生成哈夫曼樹，并將哈夫曼樹按照中序遍歷輸出。

為了保證輸出的二叉樹中序遍歷結果統一，增加以下限制：

二叉樹節點中，左節點權值小于右節點權值，根節點權值為左右節點權值之和。當左右節點權值相同時，左子樹高度小于等于右子樹高度。

注意：

所有用例保證有效，并能生成哈夫曼樹。

提醒：

哈夫曼樹又稱為最優二叉樹，是一種帶權路徑長度最短的二叉樹。

所謂樹的帶權路徑長度，就是樹中所有的葉節點的權值乘上其到根節點的路徑長度（若根節點為 0 層，葉節點到根節點的路徑長度為葉節點的層數）

輸入描述

例如：由葉子節點：5 15 40 30 10，生成的最優二叉樹如下圖所示，該樹的最短帶權路徑長度為：40 * 1 + 30 * 2 + 5 * 4 + 10 * 4 = 205。

<