企业官网建设流程全解析

看到这个标题，可能有人会觉得奇怪：字典序的第K小数字，怎么跟“十叉树的先序遍历”扯上关系了？先给结论：这俩描述的是同一个问题。题目本身很朴素——给定一个整数 n 和一个整数 k，要求返回 1 到 n 这 n 个整数里，按字典序排在第 k 位的那个数字。

什么叫字典序？简单说就是把整数当成字符串来比较：1、10、100、11、12……这些数字按字符串排序时，"10"排在"2"前面，因为开头的字符 '1' 比 '2' 小。所以数字越小不代表字典序越靠前，"10"虽然是两位数，却比个位数 "2" 更早出现。这跟正常数值排序完全是两套逻辑，刚接触时特别容易栽跟头。

这道题难的地方在于 n 可以非常大，经常到 10^9 这个量级，k 也跟着接近 10^9。如果老老实实把 1 到 n 全排序，内存和时间都撑不住。但它有一个非常漂亮的数学结构：所有数字按字典序排列时，恰好等价于一根十叉树的先序遍历结果。只要看透这层关系，就能把时间复杂度压到 O((log n)^2)，额外空间 O(1)，代码也就二十来行。接下来我就从十叉树建模开始，把思路、实现、边界条件、调试经验完整梳理一遍，适合正在刷算法题、准备面试、或者单纯对字典序排列感兴趣的朋友参考。

1. 题目拆解：为什么字典序能变成一棵树

1.1 字典序和数值序的直觉冲突

先举个具体例子。设 n=13，问你字典序第 2 小的数字是什么？按数值排序，第 2 小是 2；但按字典序排，序列是：1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9。第 2 个应该是 10，不是 2。

这就是字典序反直觉的地方：字符串比较时，先看第一位；第一位相同再看第二位。数字 10 的首位是 '1'，数字 2 的首位是 '2'，所以 10 排在 2 前面。类似地，字符串 "2" 和 "20" 相比，因为 "2" 是 "20" 的前缀，所以 "2" 更小，排前面。于是序列里会出现"2、20、21……29、3"这样的排序。

这种排序规则没法用常规的二分或排序直接处理，因为你不能简单地用"比大小"来划分区间。但换个角度想：如果每个数字后面可以无限追加 0~9 的数字，那字典序的生成过程就非常像树的遍历。

1.2 十叉树的建模过程

我们可以构造一棵十叉树：树根虚拟为一个空节点，它的子节点是 1 到 9（最高位不能是 0，所以第一层只有 9 个节点，不是 10 个）。从任意节点 cur 出发，它的子节点是 cur*10+0、cur*10+1、……、cur*10+9，一共 10 个。

举个例子，节点 1 的子节点是 10、11、12……19；节点 10 的子节点是 100、101……109。如果超出 n 的范围，对应子节点就不存在。

对这样一棵树做先序遍历（先访问节点本身，再依次访问所有子树），得到的节点序列是什么？以 n=13 为例，树的第一层是 1、2、3……9。从 1 开始：访问 1，然后访问 1 的子节点 10、11、12、13；节点 1 的子树遍历完，回到第一层访问 2；2 没有子节点（因为 20 大于 13），再访问 3……最终序列就是 1、10、11、12、13、2、3、4、5、6、7、8、9，正好和字典序一模一样。

为什么恰好一致？因为字典序的比较规则本质上就是逐位比较：当前数字是前缀时，短的排前面；否则按某个位置上的数字大小决定先后。而先序遍历恰好是"先处理当前节点，再逐个处理以它为前缀的所有数字"。树的深度对应数字的位数，同一层的兄弟节点对应同一位上的 0~9 选择，这就把字典序的递归结构完全复刻出来了。

1.3 从"枚举"到"跳子树"的关键转变

一旦意识到字典序序列是十叉树的先序遍历，问题就清晰了：我们要找的是先序遍历的第 k 个节点。最朴素的做法是从 1 开始，一个个往下走，每走一步 k 减一，走到第 k 个停止。这确实可以，但 k 太大时就退化成了 O(n) 的枚举，一秒内根本跑不完。

关键在于十叉树的密集程度：一棵子树里往往包含大量数字。比如 n=13 时，以 1 为根的子树包含 1、10、11、12、13 共 5 个数字；n=1000 时，以 1 为根的子树包含 1、10、100、1000、101……199 等一百多个数字。如果我们能快速数出某棵子树包含多少个节点，就可以直接判断目标节点是否在这棵子树里：如果在，就深入；如果不在，就整棵跳过，k 减去子树大小。这样一来，遍历的不是一个个节点，而是一棵棵子树，速度直接起飞。

这个"批量跳过"的思路，就是整道题的核心。下面拆解具体怎么实现。

2. 核心方法：getSteps 计数函数与主循环

2.1 怎么数一棵子树里的节点数

假设当前节点是 cur，我们想知道"以 cur 为根，且所有值不超过 n 的子树里，一共有多少个节点"。最直观的想法：cur 本身算一个；它的每个子节点 cur*10+i 又各自带一棵子树……递归下去就行。但递归一层层展开太慢，这里有一个经典的非递归计数方法，按层累加。

看代码前先理解一个观察：以 cur 为根的子树中，第 1 层的节点（cur 本身）落在区间 [cur, cur+1) 里；第 2 层的节点落在 [cur*10, (cur+1)*10) 里；第 3 层的节点落在 [cur*100, (cur+1)*100) 里……每往下一层，左右边界都乘以 10。因为同一层的节点，恰好是某个连续区间内所有整数。

举例，cur=1，第二层区间是 [10, 20)，也就是 10 到 19，正好是 1 的所有子节点。第三层区间是 [100, 200)，包含 100 到 199。每个区间内的数字，只要不超过 n，就都属于这棵子树；区间超出 n 的部分要截断。

于是就有了 getSteps 的代码逻辑：维护两个变量 cur 和 next，初始分别是当前节点 cur 和 cur+1；每一轮累加 min(n+1, next) - cur，代表本轮区间内实际存在的节点数；然后把 cur 和 next 都乘以 10，进入下一层，直到 cur 超过 n 为止。

2.2 计数函数的代码与手工验证

private long getSteps(int n, long cur, long next) { long steps = 0; while (cur <= n) { steps += Math.min((long) n + 1, next) - cur; cur *= 10; next *= 10; } return steps; }

注意三个细节：第一，n 要转成 long，防止 n+1 溢出；第二，cur 和 next 要用 long，因为层数加深后乘以 10 很容易超过 int 上限；第三，循环条件是 cur <= n，cur 超过 n 说明当前层已经没有节点了，直接结束。

以 n=13、cur=1、next=2 为例走一遍：

• 第一轮：cur=1，next=2，min(14,2)-1 = 1，steps = 1。统计的是节点 1 本身。
• 第二轮：cur=10，next=20，min(14,20)-10 = 4，steps = 5。统计的是 10、11、12、13 这 4 个节点。
• 第三轮：cur=100，next=200，cur 已经大于 n，退出。

结果 steps=5，和前面手推的一致。以 1 为根的子树里确实有 1、10、11、12、13 五个节点。

再验证一个容易被绕进去的例子：n=100，以 8 为根的子树有多少节点？除了 8 本身，8 的子节点是 80 到 89，一共 10 个；再下一层是 800 到 899，全部超出 n。所以总数是 11。用代码走：第一轮 min(101, 9)-8 = 1；第二轮 cur=80，next=90，min(101, 90)-80 = 10；第三轮 cur=800 大于 100 退出。累加得 11。注意这里的区间不能想当然，8 的子节点不是从 80 到 89 吗？没错，区间 [80, 90) 在 n=100 时全部有效，所以是 10 个。这就是那个关键的观察：每一层的节点都落在 [cur*10, (cur+1)*10) 这样的连续区间里。

2.3 主循环如何决定"深入"还是"跳过"

有了 getSteps，就可以设计主循环了。我们维护一个变量 cur，表示当前正在考察的节点；再维护一个 k，表示"从 cur 开始，还需要往后再走多少个位置"。初始时 cur=1，因为字典序第 1 个数字一定是 1。这里要先执行 k--，意思是 1 这个位置已经被占了，剩下要找的数字相对于 1 还要往后偏移多少。

每一轮循环：

• 计算 cur 子树的节点数 steps。
• 如果 k >= steps，说明目标不在 cur 子树里，而是排在整棵子树之后。于是 k -= steps，cur++，跳到下一个兄弟位置。
• 如果 k < steps，说明目标在 cur 子树内部。此时注意：cur 本身是子树里先序遍历的第一个节点，所以要先访问它，k--；然后进入它的第一个子节点，cur = cur * 10。

一个容易绕晕的点在第二个分支：当我们决定深入时，为什么要从 cur 跳到 cur*10，而不是跳到 cur+1？因为先序遍历的顺序是"根、左子树、右子树……"，放到十叉树里就是"当前节点、第一个子节点、第二个子节点……"。既然目标在当前节点的子树里，那么当前节点一定是目标之前的节点（或者就是目标本身），先访问掉当前节点，然后进入它的第一个子节点，继续在子树内部查找。

主循环的伪代码：

cur = 1 k = k - 1 while k > 0: steps = getSteps(n, cur, cur + 1) if k >= steps: k = k - steps cur = cur + 1 else: k = k - 1 cur = cur * 10 return cur

循环结束的条件是 k 变成 0，此时 cur 正好指向要找的那个数字。

2.4 手推一个完整例子：n=100，k=100

空对空说规则还是不够直观，我用 n=100 来完整走一遍，这是我自己调试时最爱用的测试用例，因为它的字典序序列非常有代表性。

n=100 的字典序序列是：1, 10, 100, 11, 12, ... , 19, 2, 20, ... , 29, 3, ... , 9, 90, ... , 99。可以理解为 1 的子树 12 个节点，2 到 8 各 11 个节点，9 的子树 11 个节点，合计 100 个。

初始：cur=1，k=99（因为 k=100 先做了 k--）。

• 第 1 轮：getSteps(100, 1, 2) = 12，k=99 >= 12，跳子树：k=87，cur=2。
• 第 2 轮：getSteps(100, 2, 3) = 11，k=87 >= 11，k=76，cur=3。
• 接下来 cur=3 到 7，每次跳过 11 个，k 依次变成 65、54、43、32、21。
• 第 8 轮：cur=8，getSteps(100, 8, 9) = 11，k=21 >= 11，k=10，cur=9。
• 第 9 轮：cur=9，getSteps(100, 9, 10) = 11，k=10 < 11，说明目标在 9 的子树内部。执行深入：k=9，cur=90。
• 第 10 轮：cur=90，getSteps(100, 90, 91) = 1（90 的子节点是 900，超出 n），k=9 >= 1，跳过：k=8，cur=91。
• 然后 cur=92、93、94、95、96、97、98 依次跳过 1 个节点，k 从 8 一路减到 1。
• 最后 cur=98 时，k=1 >= steps(1)，跳过后 k=0，cur=99。循环结束，返回 99。

结果和序列一致：n=100 时字典序第 100 个数字就是 99。整个过程中没有一个个枚举节点，而是大量跳过了 1、2、3 这些完整子树，只在最后一小段逐个扫过 90 到 99。这就是"按子树批量跳过"的威力。

2.5 为什么 cur++ 不会从 9 跳到 10

学习这个算法时，很多人会问：万一 cur 是 9，并且 k 依然大于等于 steps，cur++ 不就变成 10 了吗？这会不会绕回已经处理过的节点？

答案是不会。因为 9 的子树是字典序序列的末尾。以 9 为根的子树包含所有以 9 开头的数字，比如 9、90、91、92……99（或更大）。序列中所有以 1 到 8 开头的数字都排在这之前，以 9 开头的数字排最后。当 cur 走到 9 时，如果 k >= steps 成立，说明目标数字排在 9 的子树后面。但 9 的子树之后没有任何数字了，这和"k 不超过 n"矛盾。所以 k 一定落在 9 的子树内部，会走入深入分支，绝不会真的执行 cur++ 把 9 变成 10。想通这一点，整段循环的正确性就闭环了。同理，其他中间节点 cur++ 只是在兄弟之间移动或跨父节点移动，对应先序遍历的"回到父节点处理下一个兄弟"的语义，不会出现重复访问。

3. 代码实现：Java 与 Python 的完整写法

3.1 Java 实现

class Solution { public int findKthNumber(int n, int k) { int cur = 1; k--; while (k > 0) { long steps = getSteps(n, cur, (long) cur + 1); if (k >= steps) { k -= steps; cur++; } else { cur *= 10; k--; } } return cur; } private long getSteps(int n, long cur, long next) { long steps = 0; while (cur <= n) { steps += Math.min((long) n + 1, next) - cur; cur *= 10; next *= 10; } return steps; } }

主循环里只有两种操作，代码非常短，但每一行都有讲究。

• cur 的类型是 int，因为最终答案一定不超过 n，而 n 是 int。但 getSteps 里 cur 和 next 必须用 long，否则 cur*10 在 n 接近 2^31 时直接溢出成负数，循环条件 cur <= n 永远成立，死循环。
• 调用 getSteps 时我写的是 (long) cur + 1，不是 cur + 1。如果 cur 等于 Integer.MAX_VALUE（也就是 n 恰好是 int 上限），int 的 cur+1 会溢出成负数，传给 getSteps 后 next 变成负数，计数全乱。这种边界平时测不到，但面试官就喜欢问这种细节。
• 判断 k >= steps 而不是 k > steps，对应跳过整棵子树的语义：steps 表示子树里一共有多少节点，如果剩余偏移量不小于子树大小，说明整个子树都不需要再看，全部跳过。注意是"不小于"，因为当 k 正好等于 steps 时，目标恰好是子树范围内最后一个节点的下一个位置，也就是 cur 的下一个兄弟。

我自己实际提交时，就是吃了 cur+1 溢出的亏。n 用到 10^9 时还测不出来，换成 2147483647 就现原形。建议所有涉及"越界 + 1"的地方统一转 long，不要心存侥幸。

3.2 Python 实现

Python 因为整数可以任意大，省去了一堆溢出烦恼，代码更短：

def find_kth_number(n: int, k: int) -> int: cur = 1 k -= 1 while k > 0: steps = get_steps(n, cur, cur + 1) if k >= steps: k -= steps cur += 1 else: cur *= 10 k -= 1 return cur def get_steps(n: int, cur: int, next_node: int) -> int: steps = 0 while cur <= n: steps += min(n + 1, next_node) - cur cur *= 10 next_node *= 10 return steps

逻辑和 Java 版本完全一致。Python 的 min 函数参数不需要转类型，但要注意 get_steps 里 n+1 也必须在循环外算一次，不要在 min 里反复调用。

3.3 边界条件整理

整理一份我自己踩过的边界清单：

• k == 1：初始 cur=1，k-- 后 k=0，while 循环一次都不进，直接返回 1。正确。
• n <= 9：此时字典序就是 1 到 n 的数值序。比如 n=5，k=3：cur=1，k=2；getSteps(5,1,2)=1，k>=1，k=1，cur=2；getSteps(5,2,3)=1，k>=1，k=0，cur=3。返回 3。代码自然成立，不需要特判。
• n 是 10 的幂，比如 n=1000：要小心 getSteps 统计时 1000 这种数字出现的位置。以 1 为根的子树包含 1、10、100、1000、101、102……199，计数结果是 1 + 10 + 100 + 1? 不对，是 1 + 10 + 100 + 1 = 112？等一下，100 那层区间是 [100, 200)，里面包含 100 到 199 共 100 个数；再下一层 [1000, 2000) 截断到 [1000, 1001)，只含 1000 一个数。所以总数是 1 + 10 + 100 + 1 = 112。getSteps 逐层累加自动算对，但人脑核对时容易漏掉 1000 这个特殊位置。
• k 正好是整棵子树的分界点：比如 n=100，k=12 时，目标应该是 19。用代码：cur=1，k=11；getSteps=12，k<12，深入分支：cur=10，k=10；getSteps(100,10,11)=2，k>=2，k=8，cur=11；之后数到 19 时恰好 k=0。这个用例可以用来验证"深入"分支里 k-- 是否放对了位置。

3.4 主循环语义的一个反直觉点

深入分支里先 k-- 再 cur*=10，这个顺序不能换。先序遍历的精髓是"先访问根节点，再进入子树"。假设目标确实在 cur 子树内部，那么 cur 本身必然被访问到，访问它就要消耗一个偏移量，所以 k 必须减一；然后再移动到它的第一个子节点 cur*10，继续在子树中搜索。如果把顺序写成 cur*=10 再 k--，就会造成"假深入"，把 cur 的子节点当成了还没访问就消耗偏移，最终结果偏移一个位置。类似地，跳过分支里 k -= steps 和 cur++ 也不能颠倒，因为 cur++ 后对应的新子树还没开始统计，必须先扣除旧子树占用的位置。

4. 复杂度分析与拓展思考

4.1 时间复杂度为什么是 O((log n)^2)

每调用一次 getSteps，内部 while 循环会执行大约 log10(n) 次，因为每次 cur 都乘以 10。主循环每轮也会调用一次 getSteps，而主循环本身的轮数是 O(log n) 级别吗？严格说，我们需要证明主循环不会执行太多轮。

粗略理解：主循环里每一次"跳过"操作都会让 cur 前进到下一个未访问的子树，每次"深入"操作都会让 cur 乘以 10。无论哪种情况，cur 都在向目标靠近，在十叉树上的移动路径不会超过树的高度乘以一个常数。树的高度是 log10(n)，每一层最多访问几个兄弟。所以主循环轮数也是 O(log n) 级别。两者相乘，总时间复杂度 O((log n)^2)。空间上只用了几个 long 变量，O(1)。

这个结论意味着 n=10^9 时，log n 约为 9，整个算法最多执行几十次 getSteps，每次内部循环 9 轮，总计算量不到几百次，性能非常充裕。我拿 n=10^9、k=10^9 这种极端输入实测，跑下来基本是纳秒级完成。

4.2 和处理"字典序第 K 个排列"的思路对比

有一类相似的问题：给定一个字符串或数字集合，求字典序第 k 个排列。那种问题的核心做法是"康托展开"或者按位确定：每一位枚举候选字符，数一数剩余可用字符有多少种排列方式，如果 k 大于某个数量就跳过。本质也是"按块跳转"，只不过块大小的计算方式不同：排列问题的块大小是阶乘，这道题的块大小是子树节点数 getSteps。理解这一点后，可以建立一个统一的思维模型：凡是求"字典序第 k 个"的问题，都可以尝试构造一棵有序树，再通过批量跳过子树来定位节点。树的形态决定了块大小怎么算。

4.3 变体问题的迁移方法

这道题不是只能处理十叉树。如果把"每一位 0~9"改成"每一位 0~1"，那就变成二叉树的先序遍历，问题变成"二进制字符串字典序第 k 个"，getSteps 里的乘 10 改成乘 2 即可。改成十六进制也一样，乘 16。如果要求输出第 k 小的字符串而不是数字，逻辑完全不变，只是返回值类型从 int 改成 String。

还有一类常见变形：把范围从 1 到 n 改成 0 到 n，这时候虚拟根节点需要考虑 0 本身占一个位置，getSteps 和初始 cur 的选择都要调整。我的做法是先做 1 到 n 的标准版，再在答案上分情况处理 0 的特殊位置，这样不容易把主逻辑弄乱。

4.4 什么时候不适用这个模型

需要提醒一下，这个算法成立的前提是字典序按"数字字符串"比较，且所有数字都是正整数。如果题目要求的是"带前导零的等长字符串"排序，比如把 1 格式化写成 "0001"、2 写成 "0002"，那么树结构就变了，因为每个数字长度固定，前缀关系被破坏，十叉树的层数全部相等。这种情况更适合直接构造字符串数组再排序，或者用基数思想处理。千万不要生搬硬套十叉树模型。

5. 调试过程中踩过的坑与排查技巧

5.1 坑一：getSteps 里 n+1 和 cur*10 的类型溢出

这是最隐蔽的坑。我最初写的是 int，在 n 稍微大一点的时候还能跑对，但一旦 n 接近 int 上限，cur*10 直接溢出成负数，while (cur <= n) 永远成立，getSteps 陷入死循环，或者返回一个巨大的错误值。排查方法很粗暴：打印 getSteps 的输入输出，发现 n 大时 steps 变成负数才意识到溢出。

建议写代码时把所有和 10 相乘的变量、n+1 这种加减操作，一律定义为 long，不要因为当前测试数据小就放松。特别是面试手写代码时，提前声明 long 能给面试官留下"注意边界"的印象。

5.2 坑二：k-- 的初始位置

我最早写的是先把 k 保留原值，进入循环后每次访问节点才 k--，结果发现 k=1 时需要额外特判。后来改成标准写法：进入循环前先 k--，把当前节点已经占用的位置扣除。这样 k=1 时直接返回 cur=1，代码最简洁。

如果你习惯另一种写法，也不是不行，但要注意两个分支的 k 更新必须一致：要么统一用"包含当前节点偏移量"的语义，要么统一用"剩余待访问节点数"的语义。最怕的是跳过分支按子树大小扣除、深入分支却忘了扣当前节点，结果答案差 1。

5.3 坑三：手工模拟到一半迷失方向

这个题我第一次看题解时，觉得思路懂了，自己动手推 n=100 的例子却推错了好几次。后来发现最好的办法是打印调试：先用暴力法生成完整的字典序列，再让算法跑一遍，在每个循环轮次打印 cur、steps、k，和暴力序列比对。

// 调试时打印出来看，实际提交前删掉 System.out.println("cur=" + cur + ", steps=" + steps + ", k=" + k);

比如前面 n=100 的例子，暴力序列里第 89 个是 89，第 90 个是 9，第 91 个是 90。当 cur=8、k=10 时，进入 8 子树后 cur=80，k=9，如果不打印可能以为自己算错了；看到 cur 一路从 80 扫到 89，k 正好归零，才理解"先序遍历处理 8 的子树时，8 之后的第一个是 80，然后才是 81、82……89"。打印调试比空想要高效得多。

5.4 对拍验证的小建议

我调试这道题时写了一个小工具：输入 n，用 Collections.sort 生成完整字典序序列，然后随机生成几百组 k，逐组和 findKthNumber 的结果比对。这个方法能覆盖掉绝大多数边界错误。

对拍的用例建议重点覆盖几类：k=1、k=n、n 恰好是 10 的幂、n 是 10 的幂减一、n 是个位数、k 正好落在某棵子树的第一个或最后一个节点。这些位置是最容易出错的分界点，却也是最能验证算法正确性的用例。等对拍全部通过，再考虑性能优化和代码精简。

我刚接触这道题时也走了不少弯路，但把"字典序"和"十叉树"这两个概念对应上之后，整个问题一下子豁然开朗。后来遇到很多和字典序相关的问题，我都会第一时间想：能不能构造一棵树，能不能按子树批量跳过。这个思维习惯帮我解决了不少看似复杂、本质却是树的遍历的题目。如果你也想提升这方便的能力，强烈建议亲手把 n=100 的完整序列打印出来，再对照本文的代码手推一遍，这个过程比看十遍题解都管用。