<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* child[10];
    bool end;
    int num;

    TrieNode()
    {   
        end = false;
        num = -1;
        for(int i = 0; i<10; i++) child[i] = nullptr;
    }
};

class Trie
{
    
public:
    TrieNode* root;
    Trie()
    {
        root = new TrieNode();
    }
    void insert(int x, string s)
    {
        TrieNode* curr = root;

        for(char& ch : s)
        {
            if(curr->child[ch-'0'] == nullptr)
            {
                TrieNode* node = new TrieNode();

                curr->child[ch-'0'] = node;
            }
            curr = curr->child[ch-'0'];
        }
        curr->end = true;
        curr->num = x;
    }
    void get(TrieNode* root,vector<int> &res)
    {
        if(root->end == true)
        {
            res.push_back(root->num);
        }

        for(int i = 0; i<10; i++)
        {
            if(root->child[i] != nullptr)
            {
                get(root->child[i], res);
            }
        }

        return ;
    }
};
class Solution {
public:
    vector<int> lexicalOrder(int n) 
    {
        Trie t;

        for(int i = 1; i<= n; i++)
        {
            string str = to_string(i);
            t.insert(i, str);
        }

        vector<int> res;

        t.get(t.root, res);

        return res;
    }
};
25874