每日一题(2022-04-18)——字典序排数

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)
	}
}