386. Lexicographical Numbers

Given an integer n, return 1 - n in lexicographical order.

For example, given 13, return: [1,10,11,12,13,2,3,4,5,6,7,8,9].

Please optimize your algorithm to use less time and space. The input size may be as large as 5,000,000

这个题一开始看，觉得是数学问题。
//start from 1, 10, 100,101,102,103...109 then go to 11 and 110, 111...119, then go 12 and 120..129, then go to 13 and 130..139 .........then start with 2

It's actually a backtracking problem

每次数字 i*10  直到子叶结点（不能再走），走完这层的数字（+0,+1....+9），然后back to 之前那层 num+1再去下一层

The basic idea is to find the next number to add. 这点还比较好想，但是如何找下一个数字是难点。因为在某层走完之后，还要回到上一层再走下一步。所以是backtracking！！！

Take 45 for example:  the current number is 45, the next one will be 450 (450 == 45 * 10)(if 450 <= n), or 46 (46 == 45 + 1) (if 46 <= n) or 5 (5 == 45 / 10 + 1)(if5 is less than 45 so it is for sure less than n).

We should also consider n = 600, and the current number = 499, the next number is 5 because there are all "9"s after "4" in "499" so we should divide 499 by 10 until the last digit is not "9".

It is like a tree, and we are easy to get a sibling, a left most child and the parent of any node.

public List<Integer> lexicalOrder(int n) {
        List<Integer> list = new ArrayList<>(n);
        int curr = 1;
        for (int i = 1; i <= n; i++) {
            list.add(curr);
            if (curr * 10 <= n) {
                curr *= 10;
            } else if (curr % 10 != 9 && curr + 1 <= n) {
                curr++;
            } else {
                while ((curr / 10) % 10 == 9) {
                    curr /= 10;
                }
                curr = curr / 10 + 1;
            }
        }
        return list;
    }

 public class Solution {  
   List<Integer> list = new ArrayList<>();  
   public List<Integer> lexicalOrder(int n) {  
     //from 1 to n  
     //start from 1, 10, 100,1000,1001,1002...1009,101,1010,1011...1019,102,  
     //previous lenth part 1 -> 10 next part  
     //how do i know where to start next time?   
     //when we hit somthing start with 9 and couldn't been added to the list, loop end  
     dfs(n,0);  
     return list;  
   }  
   public void dfs(int n, int i){  
     if(i > n) return;  
     if(i != 0)   
       list.add(i);  
     for(int j = 0;j<=9;j++){  
       if(i!=0||j!=0)  
         dfs(n,i*10+j);  
     }  
   }  
 }