对于范围[1,n]元素，计算字典序为k的元素

所有的数字字典序元素构成一棵多叉树 通过前序遍历即可实现

class Solution {
    public int findKthNumber(int n, int k) {
//从cur=1根结点出发
        long cur=1;
        k-=1;//除去根节点
        while(k>0){
            int num=getNumber(n,cur);
            if(k<num){//表示目标结果在cur为根节点的子树中
                //结果在以cur为前缀的子结点中
                cur*=10;
                k-=1;
            }else{//否则往右兄弟节点移一位，表示节点在右兄弟节点为根节点的子树中
                cur+=1;
                k-=num;
            }
        }
        return (int)cur;//最终位置即为cur停止处
    }

    public int getNumber(int n,long cur){//计算以cur为根节点的子树中有多少节点满足在[1,n]范围的个数，一层一层地计算
        long res=0;
        long next=cur+1;
        while(cur<=n){
            res+=Math.min(next,n+1)-cur;// cur,所在层满足条件的元素个数
            cur*=10;//下一层
            next*=10;
        }
        return (int)res;
    }
}