Idea is to find the next one. The pattern is like a tree. e.g. 1's children is 10, 11, 12, ..., 19. 10's children is 101, 102, ..., 109. If any children is larger than n, then prune it away from this tree.

Then, using pre-order traversal on this tree solved the problem.

Optimization is to 1) prune the useless edges as soon as possible. 2) calculate children by multiplication.

Time: O(N) Space: O( 10 * log_10(N) )

```
class Solution(object):
def lexicalOrder(self, n):
"""
Iterative DFS.
O(N)
"""
if n <= 0:
return []
stack = range(min(n, 9), 0, -1)
ret = []
while len(stack) > 0:
cur = stack.pop()
ret.append(cur)
base = cur * 10
if base > n:
continue
for i in xrange(9, -1, -1): # 9 to 0
t = base + i
if t <= n:
stack.append(t)
return ret
```