字典树

LeetCode 440 https://leetcode.cn/problems/k-th-smallest-in-lexicographical-order/description/ 难度：困难 高频面试题汇总：https://www.yuweihung.com/posts/2025/lc-hot/ 题解参考灵神（https://leetcode.cn/problems/k-th-smallest-in-lexicographical-order/solutions/3696254/zai-shi-cha-shu-shang-zhao-di-k-xiao-olo-vzkl/）。 本题可以看成一颗十叉树。 先序遍历这棵树，等价于从左到右遍历字典序列表。所以先序遍历访问到的第 k 个节点就是答案。 每访问一个节点，就把 k 减一。当 k=0 时，当前节点就是答案。 从根节点的第一个儿子 1 开始。由于该节点被我们访问了，先把 k 减一。 设子树 1 的大小（节点个数）为 size。分类讨论： 如果 size≤k，那么答案不在子树 1 中。然后考虑下一个儿子 2，依此类推。访问到下一个儿子时，要把 k 减去 (size−1)+1=size，这里 size−1 是因为节点 1 已经访问过了。 否则，答案在子树 1 中。首先访问 1 的儿子 10，把 k 减一。依次考虑 1 的儿子 10,11,12,…,19，计算子树大小，比较子树大小与 k 的大小关系，依此类推。 问：为什么判断条件是 size≤k 而不是 size<k？ 答：因为当我们访问到子树根节点时，就把 k 减一了。这时再算子树大小，就把根节点重复统计了，所以是 size−1<k，即 size≤k。 如何计算子树大小 子树每层的节点个数是有规律的，可以逐层统计。 比如 n = 1234，计算子树 1 的大小： 第一层，只有 1 一个节点。 第二层，最小是 10，最大是 19，有 10 个节点。 第三层，最小是 100，最大是 199，有 100 个节点。 第四层，最小是 1000，最大是 n=1234，有 n−1000+1=235 个节点。 所以一共有 1+10+100+235=346 个节点。 上述过程如何用代码实现？ 每一层的最小值是好算的：1→10→100→1000。 最大值呢？看上去不太好算。 不妨改为 2→20→200→min(2000,n+1)，这个过程中的每个数减一，就是每一层的最大值。 时间复杂度：\(O(Dlog^2n)\)，其中 D=10。整棵树有 O(logn) 层，每层会遍历至多 D 个节点，每个节点需要 O(logn) 的时间计算子树大小。 空间复杂度：O(1)。 ...