多叉树应用 包括构建 dfs遍历

力扣17. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

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

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
可视化

示例 2：

输入：digits = ""
输出：[]

示例 3：

输入：digits = "2"
输出：["a","b","c"]

代码：

/*
构建多叉树，每个结点有3或4个子节点。 以digits = “23” 为例
第一个数字为2  对于字母 a b c，于是构建3颗分别以a b c为头的树
之后遍历剩余数字，如3，将3对应字母 d e f分别插入每一颗树的 每一个叶子 结点后
   a                b               c
d   e   f       d   e   f       d   e   f
之后dfs每条颗树的每条路径，加入到ans
*/


struct tree{
    char c;
    vector<tree*>next;
    tree(char cc):c(cc){}
};
void insert(tree * t,string s){  //将一棵树的每个叶结点都插入s中的字母结点
    if(t == NULL) return;   //写不写都行，初始时t肯定不空，子递归的终止条件也不是这个。
    if(t->next.size() == 0){ //如果是叶子结点，将s的每一个字符插入子节点
        for(char c : s){
            tree * tmp = new tree(c);
            t->next.push_back(tmp);
        }
        return;
    }
    for(int i = 0; i < t->next.size(); i++){  //也是dfs遍历每一个叶子结点
        insert(t->next[i],s);
    }
}
void push(vector<string>&ans,string tmp,tree * t){ //dfs多叉树
    if(t->next.size() == 0){
        tmp+=t->c;
        ans.push_back(tmp);
        return;
    }
    tmp+=t->c;
    for(int i = 0; i < t->next.size(); i++){
//因为参数传值，不是引用，所以不需要专门处理回溯，如果传引用，要将tmp+=t->c写到push上一行，在push下一在去掉最后一个字母。
        push(ans,tmp,t->next[i]);
    }
}
class Solution {
public: 
    vector<string> letterCombinations(string digits) {
        if(digits.size() == 0) return {};
        vector<string> zimu{"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"}; //下标对应号码
        char one =digits[0];  //取第一个数字，构建对应字母为头的树 3颗或4颗
        vector<tree*> first(zimu[one-'0'].size(),NULL); //将根节点放在数组
        for(int i = 0; i < zimu[one-'0'].size(); i++){  //初始化每棵树的根结点字母
            first[i] = new tree(zimu[one-'0'][i]);
        }
        for(int i = 1; i < digits.size(); i++){  //处理剩余号码
            for(int j = 0; j < first.size(); j++){  //每棵树都insert 某号码对应的个字母
                insert(first[j],zimu[digits[i]-'0']);
            }
        }
        vector<string>ans;
        string tmp = "";
        for(int i = 0; i < first.size(); i++){
            push(ans,tmp,first[i]);  //every tree path
        }
        return ans;
    }
};