<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 TrieNode{
    TrieNode* children[10];
    bool isEnd;
    TrieNode(){
        isEnd = false;
        for(int i=0;i<10;i++)
        {
            children[i] = NULL;
        }
    }
};

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

    void insert(string s)
    {
        TrieNode* curr = root;
        for(auto c:s)
        {
            int index = c - '0';
            if(curr->children[index] == NULL)
            {
                curr->children[index] = new TrieNode();
            }
            curr = curr->children[index];
        }
        curr->isEnd = true;
    }
};

class Solution {
public:
    vector<int>ans;

    void dfs(TrieNode* curr, string &temp)
    {
        if(curr->isEnd == 1)
        {
            ans.push_back(stoi(temp));
        }

        for(int i=0;i<10;i++)
        {
            if(curr->children[i])
            {
                temp += (i+'0');
                dfs(curr->children[i],temp);
                temp.pop_back();
            }
        }
    }

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

        string temp = "";
        dfs(trie.root,temp);
        return ans;
    }
};
27193