386. 字典序排数

题目：

链接：https://leetcode-cn.com/problems/lexicographical-numbers

给定一个整数 n, 返回从 1 到 n 的字典顺序。
例如，
给定 n =1 3，返回 [1,10,11,12,13,2,3,4,5,6,7,8,9] 。
请尽可能的优化算法的时间复杂度和空间复杂度。 输入的数据 n 小于等于 5,000,000。

答案：

时间：

10min

class Solution:
    def lexicalOrder(self, n: int) -> List[int]:
        ans=[]
        def dfs(k):
            if k>n:return []
            res=[k]
            for i in range(10):
                num = k*10+i
                res+= dfs(num)
            return res
        for i in range(1,10):
            ans+=dfs(i)
        return ans

要点：

1. 回溯算法

找到回溯的逻辑最重要。

2. 看成N叉树的遍历

这题看成10叉树套模板也很棒。（前序遍历）

其他：

代码报错：无