题目大意：
字典序排数
给定一个整数 n, 返回从 1 到 n 的字典顺序。
例如，
给定 n =1 3，返回 [1,10,11,12,13,2,3,4,5,6,7,8,9] 。
请尽可能的优化算法的时间复杂度和空间复杂度。 输入的数据 n 小于等于 5,000,000。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=386
解题思路分析：
题目要求将1-n的数字按照字典顺序排序，看到字典顺序这几个字我们首先要想到字典树，对于纯数字的字典树，实际上可以想象成一个十叉树，即每个数字下面都有十个子节点。比如数组1下面存在10-19这10个子节点，同理19下面存在190-199这10个子节点。总结来说，对于任意一个数字n，它都会存在n*10+0到n*10+9这10个子节点。
构建好字典十叉树之后，将字典树按照字典顺序输出实际上就是对树进行前序遍历，我们之前文章已经多次讲到过，对树形结构进行遍历的最好方式就是dfs深度优先搜索，dfs的起点有9个数字，分别是1-9，dfs的终止条件为当前点数字大于给定的数字n。
实现代码：
List<Integer> res=new ArrayList<>(); // 返回结果
public List<Integer> lexicalOrder(int n) {
// 分别以1-9作为起点开始dfs前序遍历十叉树，
for(int i=1;i<=9;i++){
help(i, n);
}
return res;
}
void help(int num, int max){
// 如果当前数字大于max，返回
if(num>max) return;
// 将当前数字加入返回结果
res.add(num);
// 将当前数字乘以10
num*=10;
// 如果大于max，返回
if(num>max) return;
// 循环dfs当前数字的10个子节点
for(int i=0;i<=9;i++){
help(num+i,max);
}
} 本题解法执行时间为1ms。
Runtime: 1 ms, faster than 100.00% of Java online submissions for Lexicographical Numbers.
Memory Usage: 45.8 MB, less than 6.67% of Java online submissions for Lexicographical Numbers.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-386-lexicographical-numbers-解题思路分析/