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]
题解：
代码语言：javascript复制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)
}
}提交结果：
