/*
1. Trie 树的前序遍历 or 直接重载判断符为字符串 都可以, 性能上Trie 好一些
*/


class Solution {

    class Trie{
        static final int BASE = 10;
        boolean isWord;
        Trie[] childs;

        public Trie() {
            this.isWord = false;
            childs = new Trie[BASE];
        }


        void put(Integer x){
            String s = String.valueOf(x);
            Trie p = this;
            for (int i = 0 ; i < s.length() ; i++){
                int index = s.charAt(i) - '0';
                if (p.childs[index] == null) p.childs[index] = new Trie();
                p = p.childs[index];
            }
            p.isWord = true;
        }
    }

    List<Integer> res = new ArrayList<>();
    StringBuilder buffer = new StringBuilder();

    public List<Integer> lexicalOrder(int n) {
        List<Integer> list = new ArrayList<>();
        Trie Trie = new Trie();
        for (int i = 1 ; i <= n ; i ++) list.add(i);
        list.forEach(Trie::put);

        res.clear();
        buffer.setLength(0);
        preOrder(Trie);
        return res;
    }

    void preOrder(Trie Trie){

        if (Trie.isWord) res.add(Integer.parseInt(buffer.toString()));

        for (int i = 0 ; i < Trie.childs.length; i ++){
            Trie c = Trie.childs[i] ;
            if (c != null){
                buffer.append(i);
                preOrder(c);
                buffer.setLength(buffer.length()-1);
            }
        }
    }
}