字典序问题

给你一个整数 n ，按字典序返回范围 [1, n] 内所有整数。

你必须设计一个时间复杂度为 O(n) 且使用 O(1) 额外空间的算法。

示例 1：
输入：n = 13
输出：[1,10,11,12,13,2,3,4,5,6,7,8,9]

思路：字典序的构建可以看成是一支十叉树

第一层是1位数字，第二层是2位数字，以此类推。

而十叉树的前序遍历即是字典序的输出

class Solution {
    List<Integer> ans = new ArrayList<>();
    public List<Integer> lexicalOrder(int n) {
        //从第一层开始
        for (int cur = 1; cur <= 9; cur++) recursion(cur, n);
        return ans;
    }
    void recursion(int cur, int limit) {
        //前序遍历的终止条件
        if (cur > limit) return ;
        ans.add(cur);
        //进入下一层
        for (int i = 0; i <= 9; i++) recursion(cur * 10 + i, limit);
    }
}

给定整数 n 和 k，返回 [1, n] 中字典序第 k 小的数字

输入: n = 13, k = 2
输出: 10
解释: 字典序的排列是 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]，所以第二小的数字是 10。

思路：其实按照第一题的思路可以解决，但是如果n十分巨大，全部遍历一遍会造成超时。

所以无需全部遍历，只需比较该节点下的子节点总数与k的大小即可

比较节点数与k的大小来判断是否需要进入子树，还是进入兄弟节点的子树

但是需要解决的问题是，有一些子树的节点不是满的，所以计算nodeCount时需要分情况

class Solution {
    public int findKthNumber(int n, int k) {
        //从第一层的第一个节点开始扫描
        int cur =1;
        k--;
        //当k==0时，证明找到节点
        while(k>0){
            long left = cur;
            long right = cur+1;
            int nodeCount = 0;
            //统计cur节点下所有子树的节点数
            while(left<=n){
                nodeCount+=Math.min(right,(int)(n+1))-left;
                left*=10;
                right*=10;
            }
            //不在cur节点下，进入另一个节点
            if(nodeCount<=k){
                k-=nodeCount;
                cur++;
            }
            else{
                //在cur节点下，进入cur的子树
                k--;
                cur*=10;
            }
        }
        return cur;
    }
}