<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>

struct Node{
    Node* links[10];
    bool flag = false;
};

class Trie{
public:
    Node* head;
    Trie(){
        head = new Node();
    }

    void insert(string s){
        Node* node = head;
        for(auto ch : s){
            if(node->links[ch - '0'] == NULL){
                node->links[ch - '0'] = new Node();
            }
            node = node->links[ch - '0'];
        }
        node->flag = 1;
    }
    
};

class Solution {
public:
    vector<int>ans;
    void dfs(Node* node, string &curr){
        if(node->flag == 1){
            ans.push_back(stoi(curr));
        }
        for(int i=0; i<10; i++){
            if(node->links[i]){
                curr += (i + '0');
                dfs(node->links[i],curr);
                curr.pop_back();
            }
        }
    }
    vector<int> lexicalOrder(int n) {
        Trie t;
        for(int i=1; i<=n; i++){
            t.insert(to_string(i));
        }
        string curr = "";
        dfs(t.head,curr);
        return ans;
    }
};
27456