<p>Given an integer <code>n</code>, return all the numbers in the range <code>[1, n]</code> sorted in lexicographical order.</p>

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

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<pre><strong>Input:</strong> n = 13
<strong>Output:</strong> [1,10,11,12,13,2,3,4,5,6,7,8,9]
</pre><p><strong class="example">Example 2:</strong></p>
<pre><strong>Input:</strong> n = 2
<strong>Output:</strong> [1,2]
</pre>
<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 5 * 10<sup>4</sup></code></li>
</ul>

class TrieNode{
public:
    TrieNode* links[10];
    bool isEnd;
    
    TrieNode(){
        for(int i=0; i<10; i++) links[i]=NULL;
        isEnd = 0;
    }

    void put(int num,TrieNode* node){
        links[num] = node;
    }

    TrieNode* get(int num){
        return links[num];
    }

    bool contains(int num){
        return links[num] != NULL;
    }
};

class Trie{
public:
    TrieNode* root;
    Trie(){
        root = new TrieNode();
    }

    void insert(int num){
        TrieNode* node = root;
        string str = to_string(num);
        int n = str.length();
        for(int i=0; i<n; i++){
            if(!node->contains(str[i] - '0')){
                node->put(str[i] - '0',new TrieNode());
            }
            node = node->get(str[i] - '0');
        }
        node->isEnd = 1;
    }

    void dfs(vector<int>& res,string str,TrieNode* node){
        if(!node) return;
        if(node->isEnd){
            res.push_back(stoi(str));
        }
        for(int i=0; i<10; i++){
            dfs(res,str+to_string(i),node->get(i));
        }
    }

    vector<int> sorted(){
        TrieNode* node = root;
        vector<int> res;
        for(int i=1; i<10; i++){
            dfs(res,to_string(i),node->get(i));
        }
        return res;
    }
};


class Solution {
public:
    vector<int> lexicalOrder(int n) {
        Trie t;
        for(int i=1; i<=n; i++) t.insert(i);
        return t.sorted();
    }
};

auto bpsn = [](){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    return 'sk';
}();
28248