看到这个标题可能有人会觉得奇怪字典序的第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 字典序和数值序的直觉冲突先举个具体例子。设 n13问你字典序第 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*100、cur*101、……、cur*109一共 10 个。举个例子节点 1 的子节点是 10、11、12……19节点 10 的子节点是 100、101……109。如果超出 n 的范围对应子节点就不存在。对这样一棵树做先序遍历先访问节点本身再依次访问所有子树得到的节点序列是什么以 n13 为例树的第一层是 1、2、3……9。从 1 开始访问 1然后访问 1 的子节点 10、11、12、13节点 1 的子树遍历完回到第一层访问 22 没有子节点因为 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) 的枚举一秒内根本跑不完。关键在于十叉树的密集程度一棵子树里往往包含大量数字。比如 n13 时以 1 为根的子树包含 1、10、11、12、13 共 5 个数字n1000 时以 1 为根的子树包含 1、10、100、1000、101……199 等一百多个数字。如果我们能快速数出某棵子树包含多少个节点就可以直接判断目标节点是否在这棵子树里如果在就深入如果不在就整棵跳过k 减去子树大小。这样一来遍历的不是一个个节点而是一棵棵子树速度直接起飞。这个批量跳过的思路就是整道题的核心。下面拆解具体怎么实现。2. 核心方法getSteps 计数函数与主循环2.1 怎么数一棵子树里的节点数假设当前节点是 cur我们想知道以 cur 为根且所有值不超过 n 的子树里一共有多少个节点。最直观的想法cur 本身算一个它的每个子节点 cur*10i 又各自带一棵子树……递归下去就行。但递归一层层展开太慢这里有一个经典的非递归计数方法按层累加。看代码前先理解一个观察以 cur 为根的子树中第 1 层的节点cur 本身落在区间 [cur, cur1) 里第 2 层的节点落在 [cur*10, (cur1)*10) 里第 3 层的节点落在 [cur*100, (cur1)*100) 里……每往下一层左右边界都乘以 10。因为同一层的节点恰好是某个连续区间内所有整数。举例cur1第二层区间是 [10, 20)也就是 10 到 19正好是 1 的所有子节点。第三层区间是 [100, 200)包含 100 到 199。每个区间内的数字只要不超过 n就都属于这棵子树区间超出 n 的部分要截断。于是就有了 getSteps 的代码逻辑维护两个变量 cur 和 next初始分别是当前节点 cur 和 cur1每一轮累加 min(n1, 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防止 n1 溢出第二cur 和 next 要用 long因为层数加深后乘以 10 很容易超过 int 上限第三循环条件是 cur ncur 超过 n 说明当前层已经没有节点了直接结束。以 n13、cur1、next2 为例走一遍第一轮cur1next2min(14,2)-1 1steps 1。统计的是节点 1 本身。第二轮cur10next20min(14,20)-10 4steps 5。统计的是 10、11、12、13 这 4 个节点。第三轮cur100next200cur 已经大于 n退出。结果 steps5和前面手推的一致。以 1 为根的子树里确实有 1、10、11、12、13 五个节点。再验证一个容易被绕进去的例子n100以 8 为根的子树有多少节点除了 8 本身8 的子节点是 80 到 89一共 10 个再下一层是 800 到 899全部超出 n。所以总数是 11。用代码走第一轮 min(101, 9)-8 1第二轮 cur80next90min(101, 90)-80 10第三轮 cur800 大于 100 退出。累加得 11。注意这里的区间不能想当然8 的子节点不是从 80 到 89 吗没错区间 [80, 90) 在 n100 时全部有效所以是 10 个。这就是那个关键的观察每一层的节点都落在 [cur*10, (cur1)*10) 这样的连续区间里。2.3 主循环如何决定深入还是跳过有了 getSteps就可以设计主循环了。我们维护一个变量 cur表示当前正在考察的节点再维护一个 k表示从 cur 开始还需要往后再走多少个位置。初始时 cur1因为字典序第 1 个数字一定是 1。这里要先执行 k--意思是 1 这个位置已经被占了剩下要找的数字相对于 1 还要往后偏移多少。每一轮循环计算 cur 子树的节点数 steps。如果 k steps说明目标不在 cur 子树里而是排在整棵子树之后。于是 k - stepscur跳到下一个兄弟位置。如果 k steps说明目标在 cur 子树内部。此时注意cur 本身是子树里先序遍历的第一个节点所以要先访问它k--然后进入它的第一个子节点cur cur * 10。一个容易绕晕的点在第二个分支当我们决定深入时为什么要从 cur 跳到 cur*10而不是跳到 cur1因为先序遍历的顺序是根、左子树、右子树……放到十叉树里就是当前节点、第一个子节点、第二个子节点……。既然目标在当前节点的子树里那么当前节点一定是目标之前的节点或者就是目标本身先访问掉当前节点然后进入它的第一个子节点继续在子树内部查找。主循环的伪代码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 手推一个完整例子n100k100空对空说规则还是不够直观我用 n100 来完整走一遍这是我自己调试时最爱用的测试用例因为它的字典序序列非常有代表性。n100 的字典序序列是1, 10, 100, 11, 12, ... , 19, 2, 20, ... , 29, 3, ... , 9, 90, ... , 99。可以理解为 1 的子树 12 个节点2 到 8 各 11 个节点9 的子树 11 个节点合计 100 个。初始cur1k99因为 k100 先做了 k--。第 1 轮getSteps(100, 1, 2) 12k99 12跳子树k87cur2。第 2 轮getSteps(100, 2, 3) 11k87 11k76cur3。接下来 cur3 到 7每次跳过 11 个k 依次变成 65、54、43、32、21。第 8 轮cur8getSteps(100, 8, 9) 11k21 11k10cur9。第 9 轮cur9getSteps(100, 9, 10) 11k10 11说明目标在 9 的子树内部。执行深入k9cur90。第 10 轮cur90getSteps(100, 90, 91) 190 的子节点是 900超出 nk9 1跳过k8cur91。然后 cur92、93、94、95、96、97、98 依次跳过 1 个节点k 从 8 一路减到 1。最后 cur98 时k1 steps(1)跳过后 k0cur99。循环结束返回 99。结果和序列一致n100 时字典序第 100 个数字就是 99。整个过程中没有一个个枚举节点而是大量跳过了 1、2、3 这些完整子树只在最后一小段逐个扫过 90 到 99。这就是按子树批量跳过的威力。2.5 为什么 cur 不会从 9 跳到 10学习这个算法时很多人会问万一 cur 是 9并且 k 依然大于等于 stepscur 不就变成 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 的 cur1 会溢出成负数传给 getSteps 后 next 变成负数计数全乱。这种边界平时测不到但面试官就喜欢问这种细节。判断 k steps 而不是 k steps对应跳过整棵子树的语义steps 表示子树里一共有多少节点如果剩余偏移量不小于子树大小说明整个子树都不需要再看全部跳过。注意是不小于因为当 k 正好等于 steps 时目标恰好是子树范围内最后一个节点的下一个位置也就是 cur 的下一个兄弟。我自己实际提交时就是吃了 cur1 溢出的亏。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 里 n1 也必须在循环外算一次不要在 min 里反复调用。3.3 边界条件整理整理一份我自己踩过的边界清单k 1初始 cur1k-- 后 k0while 循环一次都不进直接返回 1。正确。n 9此时字典序就是 1 到 n 的数值序。比如 n5k3cur1k2getSteps(5,1,2)1k1k1cur2getSteps(5,2,3)1k1k0cur3。返回 3。代码自然成立不需要特判。n 是 10 的幂比如 n1000要小心 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 正好是整棵子树的分界点比如 n100k12 时目标应该是 19。用代码cur1k11getSteps12k12深入分支cur10k10getSteps(100,10,11)2k2k8cur11之后数到 19 时恰好 k0。这个用例可以用来验证深入分支里 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)。这个结论意味着 n10^9 时log n 约为 9整个算法最多执行几十次 getSteps每次内部循环 9 轮总计算量不到几百次性能非常充裕。我拿 n10^9、k10^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 里 n1 和 cur*10 的类型溢出这是最隐蔽的坑。我最初写的是 int在 n 稍微大一点的时候还能跑对但一旦 n 接近 int 上限cur*10 直接溢出成负数while (cur n) 永远成立getSteps 陷入死循环或者返回一个巨大的错误值。排查方法很粗暴打印 getSteps 的输入输出发现 n 大时 steps 变成负数才意识到溢出。建议写代码时把所有和 10 相乘的变量、n1 这种加减操作一律定义为 long不要因为当前测试数据小就放松。特别是面试手写代码时提前声明 long 能给面试官留下注意边界的印象。5.2 坑二k-- 的初始位置我最早写的是先把 k 保留原值进入循环后每次访问节点才 k--结果发现 k1 时需要额外特判。后来改成标准写法进入循环前先 k--把当前节点已经占用的位置扣除。这样 k1 时直接返回 cur1代码最简洁。如果你习惯另一种写法也不是不行但要注意两个分支的 k 更新必须一致要么统一用包含当前节点偏移量的语义要么统一用剩余待访问节点数的语义。最怕的是跳过分支按子树大小扣除、深入分支却忘了扣当前节点结果答案差 1。5.3 坑三手工模拟到一半迷失方向这个题我第一次看题解时觉得思路懂了自己动手推 n100 的例子却推错了好几次。后来发现最好的办法是打印调试先用暴力法生成完整的字典序列再让算法跑一遍在每个循环轮次打印 cur、steps、k和暴力序列比对。// 调试时打印出来看实际提交前删掉 System.out.println(cur cur , steps steps , k k);比如前面 n100 的例子暴力序列里第 89 个是 89第 90 个是 9第 91 个是 90。当 cur8、k10 时进入 8 子树后 cur80k9如果不打印可能以为自己算错了看到 cur 一路从 80 扫到 89k 正好归零才理解先序遍历处理 8 的子树时8 之后的第一个是 80然后才是 81、82……89。打印调试比空想要高效得多。5.4 对拍验证的小建议我调试这道题时写了一个小工具输入 n用 Collections.sort 生成完整字典序序列然后随机生成几百组 k逐组和 findKthNumber 的结果比对。这个方法能覆盖掉绝大多数边界错误。对拍的用例建议重点覆盖几类k1、kn、n 恰好是 10 的幂、n 是 10 的幂减一、n 是个位数、k 正好落在某棵子树的第一个或最后一个节点。这些位置是最容易出错的分界点却也是最能验证算法正确性的用例。等对拍全部通过再考虑性能优化和代码精简。我刚接触这道题时也走了不少弯路但把字典序和十叉树这两个概念对应上之后整个问题一下子豁然开朗。后来遇到很多和字典序相关的问题我都会第一时间想能不能构造一棵树能不能按子树批量跳过。这个思维习惯帮我解决了不少看似复杂、本质却是树的遍历的题目。如果你也想提升这方便的能力强烈建议亲手把 n100 的完整序列打印出来再对照本文的代码手推一遍这个过程比看十遍题解都管用。