# Trie DFS and O(n) iterative

• Build a Trie

``````class Solution {
public:
class TrieNode {
public:
char d;
vector<TrieNode*> nextTable;
bool output;
TrieNode(char c) :d(c) {
nextTable.resize(10, 0);
output = false;
}
};

void insertNum(TrieNode *head, string &s) {
for (int i = 0; i < s.size(); i++) {
int id = s[i] - '0';
if (!cur->nextTable[id]) {
cur->nextTable[id] = new TrieNode(s[i]);
}
cur = cur->nextTable[id];
}
cur->output = true;
}

void dfs(TrieNode *cur, int val, vector<int> &collector) {
if (!cur) return;
int curVal = val * 10 + cur->d - '0';
if (cur->output) {
collector.push_back(curVal);
}

for (int i = 0; i < cur->nextTable.size(); i++) {
dfs(cur->nextTable[i], curVal, collector);
}
}

vector<int> lexicalOrder(int n) {
for (int i = 1; i <= n; i++) {
string s = to_string(i);
}
vector<int> ret;
return ret;
}
};
``````

O(n) get Next value

``````class Solution {
public:
vector<int> lexicalOrder(int n) {
vector<int> ret(n, 0);
int cur = 1;
int i = 0;
while (i < n) {
ret[i++] = cur;

//getNext
if (cur * 10 <= n) {
cur *= 10;
} else {
if (cur == n) {
cur /= 10;
}
cur++;
while ((cur % 10) == 0) {
cur /= 10;
}
}
}
return ret;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.