本地手机网站建设百度招聘
在我们的座机上，都有这种数字与字母对应的按键。
以此为例，讲解多叉树的深度优先遍历
问题
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1：
输入：digits = "23" 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：
输入：digits = "" 输出：[]
示例 3：
输入：digits = "2" 输出：["a","b","c"]
0 <= digits.length <= 4digits[i]是范围['2', '9']的一个数字。
分析
假设我们输入的是 2 5 8 那么对应元素分别是abc jkl tuv。一共有3*3*3 = 27钟组合。我们的思路是
先从2中取a，再从5中取j，再从8中取t。将三个字母存放到一个字符串中。再将不断组合好的字符串push_back到vector<string>中
完成好一组之后，到达最深再返回，再组合a j u；再push_back。
代码
class Solution {
private:const char* numStrArr[10]= {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"}; //存放字符串的数组public:void Combine(const string& digits, int i, string combineStr,vector<string>& ret){if (i == digits.size()) //深度遍历{ret.push_back(combineStr);return;}int num = digits[i] - '0';string str =numStrArr[num]; //数字映射的字母for (auto ch : str) //取一个字符，去排列组合{Combine(digits,i+1,combineStr+ch,ret);}}vector<string> letterCombinations(string digits) {vector<string> v; //存放字符串组合string str; if (digits.empty())return v;Combine(digits,0, str,v);return v;}
};几个对象的功能digits,0, str,v
digits：存储输入的字符串
0：作为下标，不断遍历字符串，知道到达size()为止
str：将映射好的数据存储到str中
v:返回数组
核心代码
string str =numStrArr[num]; //数字映射的字母
for (auto ch : str) //取一个字符，去排列组合
{
Combine(digits,i+1,combineStr+ch,ret);
}
假设还是 2 5 8 。取到2的首字母之后，进入递归，取5的首字母。继续递归取到8的首字母。
再push_back
回到循环，继续取8的第二个字母
等到5的首字母取完之后，再取5的第二个字母，继续递归。
剖解代码
通过上述的分析，我们可以得出，
1.需要靠一个递归完成遍历。递归的返回条件是深度达到size（）
2.既然是数字与字母的映射，那就需要借助下标去不断遍历读取到的字符串
3.在不断加深的过程中，应该靠的是 + 而不是+=，这样return之后，就可以回到原来的字符串
经验总结
当我们直接上手，可能不会那么容易。但是显然的是，这是存放在容器中的数据。因此理所应到要去考虑到用什么类型的数据结构去存放数据。从而想到该用什么方式去遍历。
对于树，最好的方法就是递归遍历（想好返回条件）。
其次：
1.最终要的是，递归要分析好return条件
2.当需要深度遍历时，一般需要借助下标 i
3.用到的是+ 而不是+=