# 386. 字典序排数 DFS深度優先 模板【Medium】【DFS】

DFS模板
dfs是一種遞迴，所以要設定遞迴的終止條件，且方法互相call時，要做事，才有意義。
1. Base case
Do something
Recurse for subproblems

General steps:
1. Base Case **(Leaf)**
2. 利用父問題傳下來的值做一些計算 **(parent node multiple 10 and add node val) cur = cur*10+node.val < limit**
3. 若有必要，做一些額外操作
4. 返回答案(給父問題) **dfs(cur, limit)**


public void dfs(TreeNode node){
    if(node == null){
        return;
    }
    System.out.println(node.val);
    dfs(node.left);
    dfs(node.right);
}

给你一个整数 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 = 2
输出：[1,2]

題解思路：
將[1,n]的數按照字典序加入到答案，本質上是對一顆節點數量為n，類型類似字典樹的多階樹進行遍歷。
根節點是0，所以需要跳過，可以從樹的第二層開始搜索

class Solution {
    List<Integer> ans = new ArrayList<>();
    public List<Integer> lexicalOrder(int n) {
        for(int i=1;i<=9;i++){
            dfs(i, n);
        }
        return ans;
    }
    void dfs(int cur, int limit){
        if(cur>limit) return;
        ans.add(cur);
        for(int i=0;i<=9;i++){
            dfs(cur*10+i, limit);
        }
    }
}