04080:Huffman编码树

greedy, http://cs101.openjudge.cn/practice/04080/

思路：根据huffman编码的定义，每次将权重最小的两个合并成一个，一直合并直到最后只剩一个，该节点即为根节点

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

struct TreeNode
{
    int weight;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int w) : weight(w), left(nullptr), right(nullptr) {}
    TreeNode(int w, TreeNode* l, TreeNode* r) : weight(w), left(l), right(r) {}
};
class Solution
{
    public:
        vector<pair<int,TreeNode*>> heights;
        void getheights()
        {
            int length;
            cin >> length;
            heights.resize(length);
            for (int i = 0; i < length; i++)
            {
                cin >> heights[i].first;
                heights[i].second = new TreeNode(heights[i].first);
                //一定是叶节点，因此可以直接建立
            }
        }
        void buildTree(vector<pair<int, TreeNode*>>& heights)//这个&我debug了半天才发现没写
        {
            while (heights.size() > 1)
            {
                sort(heights.begin(), heights.end());
                TreeNode* left = heights[0].second;
                TreeNode* right = heights[1].second;
                int sum = heights[0].first + heights[1].first;
                heights.erase(heights.begin(), heights.begin() + 2);
                heights.push_back({sum, new TreeNode(sum, left, right)});
                //合二为一，一为二的父节点
            }
        }
        int length(TreeNode* root, int height)
        {
            if (!root) return 0;//理论上这行不会执行
            if (root->left == nullptr && root->right == nullptr)//叶节点
                return (height * root->weight);
            return length(root->left, height + 1) + length(root->right, height + 1) ;
        }
        void solve()
        {
            getheights();
            buildTree(heights);
            cout << length(heights[0].second, 0);
        }
};
int main() 
{
    Solution s;
    s.solve();
    return 0;
}