Given an integer n, return all the numbers in the range [1, n] sorted in lexicographical order.

You must write an algorithm that runs in&nbsp;O(n)&nbsp;time and uses O(1) extra space.&nbsp;

&nbsp;
Example 1:
Input: n = 13
Output: [1,10,11,12,13,2,3,4,5,6,7,8,9]
Example 2:
Input: n = 2
Output: [1,2]

&nbsp;
Constraints:


	1 &lt;= n &lt;= 5 * 104


class Solution:
    def lexicalOrder(self, n: int) -> List[int]:
        result = []
        orderDic = {}
        for i in range(1, n + 1):
            strI = str(i)
            level = orderDic
            for char in strI:
                if char not in level:
                    level[char] = {}
                level = level[char]
        self.traverse(orderDic, "", result)
        return result
        
    def traverse(self, dic, temp, result):
        for key in dic:
            result.append(int(temp + key))
            self.traverse(dic[key], temp + key, result)
class Solution {

    private final TrieNode trie = new TrieNode(' ');

    class TrieNode{

        private Character digit;
        private String value;
        private boolean isWord;
        private Map<Character, TrieNode> children;

        TrieNode(Character c){
            this.digit = c;
            this.isWord = false;
            this.children = new HashMap<>();
        }

        void insert(String s){
            TrieNode current = this;
            for(Character c : s.toCharArray()){
                current = current.children.computeIfAbsent(c, k -> new TrieNode(c));
            }
            current.value = s;
            current.isWord = true;
        }

        List<Integer> getWordsPreOrder(){
            return getWordsPreOrder(this);
        }

        private List<Integer> getWordsPreOrder(TrieNode root){
            List<Integer> result = new ArrayList<>();
            if(root == null){
                return result;
            }

            if(root.isWord){
                result.add(Integer.parseInt(root.value));
            }
            for(TrieNode node : root.children.values()){
                result.addAll(getWordsPreOrder(node));
            }
            return result;
        }
    }

    public List<Integer> lexicalOrder(int n) {
        for(int i = 1 ; i<=n;i++){
            trie.insert(String.valueOf(i));
        }
        return trie.getWordsPreOrder();
    }
}
class Solution {
private:
    void dfs(int i, int n, vector<int> &ans){
        if(i > n) return;
        ans.push_back(i);
        for(int j = 0; j< 10; ++j) dfs(i * 10 + j, n, ans);
    }
public:
    vector<int> lexicalOrder(int n) {
        vector<int> ans;
        for(int i =1; i<10; ++i) dfs(i, n, ans);
        return ans;
    }
};
/**
 * @param {number} n
 * @return {number[]}
 */
var lexicalOrder = function(n) {
    const arr = [];
    
    function dfs(baseIndex) {
        if (baseIndex * 10 > n) {
            return;
        }
        
        for(let i = baseIndex * 10; i < baseIndex * 10 + 10 && i <= n; i++)  {
           arr.push(i);
           dfs(i);
        }
    }
    
    let stack = [];
    
    for(let i = 1; i <= 9 && i <= n; i++) {
        arr.push(i);        
        dfs(i);
    }
    
    return arr;
};
Lexicographical Numbers