<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:
    int val;
    TrieNode* children[10];
    bool is_end=false;

    TrieNode(int value){
        val=value;
        for(int i=0;i<10;i++){
            children[i]=nullptr;
        }
        is_end=false;
    }
};




class Solution {
public:
    TrieNode* root;
    Solution(){
        root=new TrieNode(-1);
    }
    void insert(TrieNode*root,int input){
        string s=to_string(input);
        TrieNode* current=root;
        for(auto i:s){
            int index=i-'0';
            if(!current->children[index]){
                current->children[index]=new TrieNode(index);
            }
            current=current->children[index];
        }
        current->is_end=true;
    }
    void helper(TrieNode* root,int curr,vector<int>&result){
        if(!root) return;
        if(root->is_end) result.push_back(curr);
        for(int i=0;i<10;i++){
            if(root->children[i]){
                helper(root->children[i],10*curr+i,result);
            }
        }
    }
    vector<int> lexicalOrder(int n) {
        for(int i=1;i<=n;i++){
            insert(root,i);
        }
        vector<int>result;
        helper(root,0,result);
        return result;

    }
};
26929