<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 Solution {
public:
struct Node{
    Node* links[10];
    bool flag=false;
    bool containsKey(char ch){
        return links[ch-'0']!=NULL;
    }
    void put(char ch, Node* node){
        links[ch-'0'] = node;
    }
    Node* get(char ch){
        return links[ch-'0'];
    }
    void setEnd(){
        flag = true;
    }
    bool getEnd(){
        return flag;
    }
};
class Trie{
public:
    Node* root;

    Trie(){
        root = new Node();
    }
    void insert(string& num){
        Node* temp = root;
        for(int i=0; i<num.size(); i++){
            if(!temp->containsKey(num[i])){
                temp->put(num[i], new Node());
            }
            temp = temp->get(num[i]);
        }
        temp->setEnd();
    }
};

    void dfs(Node* root, int curr, vector<int>& ans){
        if(root==NULL){
            return;
        }
        if(root->getEnd()==true){
            ans.push_back(curr);
        }
        for(char ch='0'; ch<='9'; ch++){
            if(root->containsKey(ch)){
                dfs(root->get(ch), (curr*10)+(ch-'0'), ans);
            }
        }
    }

    vector<int> lexicalOrder(int n) {
        Trie trie;
        for(int i=1; i<=n; i++){
            string s = to_string(i);
            trie.insert(s);
        }

        vector<int> ans;
        dfs(trie.root,0,ans);
        return ans;
    }
};
25083