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;
}
上一篇:LeetCode 844 比较含退格的字符串


下一篇:30 Day Challenge Day 12 | Leetcode 198. House Robber