原题出处：https://leetcode.cn/leetbook/read/top-interview-questions-medium/xv8ka1/

解法一:

class Solution {
    public List<String> letterCombinations(String digits) {
        LinkedList<String> res = new LinkedList<>();
        if (digits == null || digits.isEmpty()) {
            return res;
        }
        char[][] tab = {{'a', 'b', 'c'}, {'d', 'e', 'f'}, {'g', 'h', 'i'},
                {'j', 'k', 'l'}, {'m', 'n', 'o'}, {'p', 'q', 'r', 's'},
                {'t', 'u', 'v'}, {'w', 'x', 'y', 'z'}};
        res.add("");
        while (res.peek().length() != digits.length()) {
            String remove = res.poll();
            char[] chars = tab[digits.charAt(remove.length())-'2'];
            for (int i = 0 ; i < chars.length; i++) {
                res.add(remove + chars[i]);
            }
        }
        return res;
    }
}

思路：bfs，联想一颗n差树，广度优先。

每一个数字对应3到4个字符，我们以示例一为例画个图来看一下

我们看到实际上就是一颗n叉树，除了叶子节点外，每个节点都有3到4个子节点。

实际上这题给的并不是一棵树，这棵树只是我们想象的，那我们怎么确定走到叶子节点了呢，实际上很简单，如果有n个数字，那么叶子节点字符串的长度就应该是n。

二叉树的BFS遍历代码如下：

public void levelOrder(TreeNode tree) {
 //链表，这里我们可以把它看做队列
    LinkedList<TreeNode> list = new LinkedList<>();
    list.add(tree);//相当于把数据加入到队列尾部
    while (!list.isEmpty()) {
      //poll方法相当于移除队列头部的元素
        TreeNode node = list.poll();
        //访问当前节点
        System.out.println(node.val);
        //遍历当前节点的左子节点和右子节点
        if (node.left != null)
            list.add(node.left);
        if (node.right != null)
            list.add(node.right);
    }
}

n叉树的BFS遍历代码如下：

public void levelOrder(TreeNode tree) {
    //链表，这里我们可以把它看做队列
    LinkedList<TreeNode> list = new LinkedList<>();
    list.add(tree);//相当于把数据加入到队列尾部
    while (!list.isEmpty()) {
        //poll方法相当于移除队列头部的元素
        TreeNode node = list.poll();
        //访问当前节点
        System.out.println(node.val);
        //遍历当前节点的所有子节点
        for (int i = 0; i < node.child.count; i++) {
            list.add(node.child[i]);
        }
    }
}