[Java知识库]leetcode 386. Lexicographical Numbers | 386. 字典序排数（Java）

题目

https://leetcode.com/problems/lexicographical-numbers/

题解

思路：先序遍历 10 叉树，参考：Simple Java DFS Solution

The idea is pretty simple. If we look at the order we can find out we just keep adding digit from 0 to 9 to every digit and make it a tree.
Then we visit every node in pre-order. 
       1        2        3    ...
      /\        /\       /\
   10 ...19  20...29  30...39   ....

class Solution {
    public List<Integer> lexicalOrder(int n) {
        ArrayList<Integer> res = new ArrayList<>();
        for (int i = 1; i < 10; i++) {
            dfs(i, n, res);
        }
        return res;
    }

    public void dfs(int num, int max, List<Integer> list) {
        if (num > max) return;
        list.add(num);
        for (int i = 0; i < 10; i++) {
            if (num * 10 + i > max) return;
            dfs(num * 10 + i, max, list);
        }
    }
}