LC386. 字典树排序

思路：DFS遍历字典树

• 此题的关键在于，隐性维护了一个字典树，这一点是理解思路的关键。
• 树的每一层都有个孩子节点，分别是到，每读到下一层，，如果这个数值比大，就不记录，否则就记录。

  

  

  代码：

class Solution:
    # 维护了一个隐性的字典树，只要对其进行dfs即可
    def lexicalOrder(self, n: int) -> List[int]:
        recVal = list()
        def dfs(curVal: int, curDepth: int) -> None:
            if curVal > n or (curVal == 0 and curDepth != 0):
                return
            if curDepth > 0:
                recVal.append(curVal)
            for i in range(10):
                dfs(curVal * 10 + i, curDepth + 1)
        dfs(0, 0) 
        return recVal