电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例:

输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

说明:
尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

---

分析：

    把输入的字符串表示的数字当成N叉树来做，进行层次遍历就可以了。比如输入的是“23”，就当成如下所示的深度为2的树来做

   a             b              c

d e f        d e f         d e f

然后进行层次遍历，就得到了结果 "ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"。

但是上图所示的树并不是一个真正的树，而是一个森林，因为树只有一个根节点，所以，为了统一操作，我们给他加一个没有字符的头节点’‘，就把森林转化成了树。比如输入的还是“23”，那么就当成如下所示深度为3的树来做

                 ‘ ’

   a             b              c

d e f        d e f         d e f

进行层次遍历对应的字符，得到的结果还是 "ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"

class Solution {
public:
    vector<string> letterCombinations(string digits) {
//         当成N叉树进行层次遍历
        
//         保存结果
        vector<string> result;
        if(digits.length() <= 0) return result;
//         层次遍历的辅助队列
        queue<string> save_result;
        save_result.push("");   // 初始结果
//         进行层次遍历
        order_depth(digits,0,save_result);
//         遍历结果
        while(!save_result.empty()){
            result.push_back(save_result.front());
            save_result.pop();            
        }
        return result;
    }
    
//     层次遍历
    void order_depth(string digits, int depth, queue<string>& save_result){        
        if(depth >= digits.length()) return;    // 超过了树的深度
        
        string char_str = getStr(digits[depth]);    // 保存当前字母表示的数字
        
        int size = save_result.size();
        while(size){
            string pre_result = save_result.front();  // 得到上一层的结果
            save_result.pop();  // 弹出
    //         保存这一层的结果
            for(int i=0; i<char_str.length(); i++){
                save_result.push(pre_result + char_str[i]);
            }
            size --;
        }
//         下一层
        order_depth(digits, depth+1, save_result);
    }
    
//     获得相应的字母表示的string
    string getStr(char ch){
        switch(ch){
            case '2':return "abc";
            case '3':return "def";
            case '4':return "ghi";
            case '5':return "jkl";
            case '6':return "mno";
            case '7':return "pqrs";
            case '8':return "tuv";
            case '9':return "wxyz";
        }
        return "";
    }
};