440. 字典序的第K小数字（十叉树）

class Solution {

    // 十叉数
    public int findKthNumber(int n, int k) {
        int cur = 1;
        k--; // 初始化cur为第一个数，所以要k--
        while(k > 0) { 
            long left = cur, right = cur + 1, sum = 0; // long防止*10溢出
                                    // 计算本分支和下一个分支（本分支加一）之间总共有多少个数
            while(left <= n) {
                sum += Math.min(right, (long)n + 1) - left; // 计算每一层的个数
                left *= 10;  // 依次向下层走
                right *= 10;
            }
            if(sum > k) {  // 判断总数是否大于k若大于k肯定在本分支，所以继续向下走cur * 10
                cur *= 10;
                k--;
            } else { // 小于等于k说明在下一个分支，向右走cur++
                cur++;
                k -= sum;
            }
        }
        return cur;
    }
}