30 Day Challenge Day 7 | Hackerrank: Tree: Huffman Decoding

题解

事实证明，这种有着详实背景介绍的题干，大部分与算法本身无关，反而是直接看sample input和output更容易理解题目要求。

同时，也证明，用sample进行手动debug很有效。

一旦意思理解了，题目似乎并不难。也就是根据0/1移动至当前节点的左右节点，一旦遇到叶子节点，便把对应数据更新到结果中。

void decode_huff(node * root, string s) {
    string ret;
    node* curr = root;
    int i = 0;
    while(i < s.size()) {

        // move until leaf node
        if(s[i] == '0') {
            curr = curr->left;
        } else {
            curr = curr->right;
        }

        if(!curr->left && !curr->right) {
            // leaf node then append to output
            ret += curr->data;
            curr = root;
        }

        i++;
    }
    cout << ret << endl;
}