共计 1943 个字符，预计需要花费 5 分钟才能阅读完成。
给你一个整数 n，按字典序返回范畴 [1, n] 内所有整数。你必须设计一个工夫复杂度为 O(n) 且应用 O(1) 额定空间的算法。相干标签：深度优先搜寻，字典树；提醒：1 <= n <= 5 * 10^4。
Tire 树（又称单词查找树）简介：是一种树形构造，是一种哈希树的变种。典型利用于统计，排序和保留大量的字符串（但不仅限于字符串），所以常常被搜索引擎零碎用于文本词频统计。它的长处是利用字符串的公共前缀来缩小查问工夫，最大限度地缩小无谓的字符串比拟，查问效率比哈希树高，毛病是空间复杂度比拟大。优化：咱们能够用链表来动静开拓空间，达到空间上利用率的最大化。
Tire 树的性质：根结点不蕴含字符，其余的每一个节点只蕴含一个字符；从根结点到某一节点，门路上通过的字符连接起来，为该节点对应的字符串（如果某个节点为一个字符串的结尾，对其打个标记即可）。每个节点的所有子节点蕴含的字符都不雷同。
请留神在这题咱们用一个 trie 树来示意所有的数，如果以后数是在 1−n 范畴内的，就插入到答案中。因为示意了所有数，所以没必要模仿一个 trie 数并且插入。所以咱们只须要模仿一个在 trie 上树搜寻即可。工夫复杂度 O(N)。tire 树还不懂的本人轻易在网上找张 tire 树的图看看就了解了。
这题的话就是给咱们 n 个数，让咱们把 n 个数依照字典序排一下，留神不是按数的大小来排而是按字典序的大小来排。力扣这题本来的数据范畴很大有 5,000,000（五百万）然而当初只剩下 50,000（五万）了。
字典序的含意比较简单，这里就不放长概念了粗略的阐明一下。比如说 88 和 123，依照数字大小来比拟的话 88 必定是小于 123 的，然而依照字典序的话 88 就大于 123，因为是比拟每一位的字符大小，简略粗犷的了解就是这个意思，想晓得更多的话就本人去百度吧。
接下来咱们探讨解题办法，首先最暴力的做法就是把 1～n 个数先转化为 string 看成字符串，而后你对 string 排序就能够了。那么这么做的工夫复杂度是多少呢？首先每一个数的长度是 log n 是吧，而后快排的工夫复杂度是 nlog n，所以总共的工夫复杂度就是一乘就是 nlog n^2，这是暴力做法。而后比拟优良的做法是能够用 tire 来做，留神此 tire 非彼 tire，tire 啥意思呢。
tire 的意思咱们上文曾经讲过了，个别字符串排序用 tire 排序的话工夫复杂度能少一个 log n，tire 其实就相似于桶排序。那么这个 tire 是怎么样的一个思路呢，就是这样咱们先将所有数看成一个字符串。比方 123、124 还有 12 都是一个字符串，而后咱们把他们插到这个树外面，而后咱们能够设想一下将 1～n 插入到这个串外面，而不是咱们在程序设计中真的插入这些数。
设想完把下面数插入到这个串外面，而后插完之后怎么去依照字典序从小到大输入呢？这个其实就是一个树的遍历，如果咱们想找到 tire 外面所有数的话，其实就是一个树的遍历，那么为了可能从小到大的去输入所有数，就比方咱们有几个分支是吧，为了保障咱们的字典序最小，那么咱们再搜的时候第一个数应该是越小越好是吧，所以咱们在搜的时候要从小到大搜寻每一个分支，那这样只有你依照咱们这个思路来搜的话，那么你搜到的后果肯定是依照字典序的后果。
因为咱们会先搜 1 再搜 2 再搜 3 是吧，那么以 1 结尾的子树必定会比左边的树都要小，因为它第一个曾经小了是吧。所以说咱们只有依照字典序去搜这棵树，咱们就能够把所有数依照字典序搜进去。好吧，那么这个就是 tire 树的一个大略的思路，那么这个思路的话首先遍历整个树的工夫复杂度是 n logn 是吧，因为整棵树外面的结点的个数就是 n log n 是吧，而后咱们找进去所有数的工夫复杂度也是 nlog n，所以整个整个算法工夫复杂度就是 nlog n，比咱们之前的暴力做法要小一个 log n。留神咱们在写的时候不须要真的把咱们所有的数插入到咱们这个 tire 树外面。它插入到时候很有法则是 1～n 间断插入，所以咱们就不须要插入了。而后咱们在搜的时候咱们假如每个分支都有，只不过咱们去判断一下如果以后这个分支的数大于 n 了，那么这个前面的数也肯定大于 n 是吧，就间接进行就能够了就不必持续往下搜了，所以这题咱们是不须要真正的插入的，咱们只须要在查问的时候限定一下范畴就能够了。
而后是代码怎么写：
class Solution {
public:
vector<int> res;
vector<int> lexicalOrder(int n) {for(int i=1;i<=9;i++) dfs(i,n);
return res;
}
void dfs(int cur,int n) {if(cur <= n) res.push_back(cur);
else return;
for(int i=0;i<=9;i++) dfs(cur*10+i,n);
}
};
