386. 字典序排数
题目描述：
给你一个整数 n ，按字典序返回范围 [1, n] 内所有整数。
你必须设计一个时间复杂度为 O(n) 且使用 O(1) 额外空间的算法。
示例1：
输入：n = 13
输出：[1,10,11,12,13,2,3,4,5,6,7,8,9]
示例2：
输入：n = 20
输出：[1,10,11,12,13,14,15,16,17,18,19,2,20,3,4,5,6,7,8,9]
思路：
解释：
以例二来看：
可以看到字典序的遍历，就是树的深度优先遍历(先序遍历)DFS，只是本题不是以0为根的数，而是以1~9为根的，9棵十叉树，我们只需要对着就9棵树分别进行深度优先遍历(DFS)，就可以得到对应字典序。
输入：n = 20
输出：[1,10,11,12,13,14,15,16,17,18,19,2,20,3,4,5,6,7,8,9]
题解：
func lexicalOrder(n int) []int { res:=make([]int,0) // 1~9 现在有9棵树 for i := 1; i <= 9; i++ { // 对每棵树都进行 dfs 深度优先遍历 dfs(i, n, &res) } return res } // cur 当前节点 n 最大值 res 结果集 func dfs(cur int, n int, res *[]int) { // 如果当前节点的值大于最大值，说明不可以再继续深入了 if cur > n { return } // 深度优先遍历 先对当前节点操作，再继续对当前节点继续深度优先遍历 *res = append(*res, cur) // 每个节点有 0~9 10个孩子 for i := 0; i < 10; i++ { // cur是当前值，cur*10+i是走到i这个节点后的值, // 如果大于最大值,就返回,如果仍小于，说明可以继续深度优先搜索 if cur*10+i > n { return } // 这里填cur*10+1 意思是来到了i这个节点，并对i这个节点的孩子继续进行深度优先搜素 dfs(cur*10+i, n, res) } }
提交结果：
