本文主要是介绍Leetcode 440 K-th Smallest in Lexicographical Order n叉树快速按层遍历，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Given integers n and k, find the lexicographically k-th smallest integer in the range from 1 to n.
Note: 1 ≤ k ≤ n ≤ 109.
Example:
Input:
n: 13 k: 2Output:
10Explanation:
The lexicographical order is [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9], so the second smallest number is 10.
Accepted
10,496
Submissions
37,795
这个问题注意几点：
1. 刚好遍历是颗按照深度优先遍历阉割的n叉树
2. 假设这一层节点全满，这一层有效节点的个数是next-pre；如果不满，只能去找兄弟节点
3. 因此，按层遍历树可以很方便地求以某个pre为前缀的有效个数step
4. 如果这个step<=k，说明以res为前缀的子树没有累积到，去res的兄弟节点找，否则去res的孩子找
最后上代码：
class Solution:def findKthNumber(self, n, k):k -= 1res = 1while k > 0:step, pre, next = 0, res, res+1# 实际上按层遍历while pre <= n:# 以res为前缀的子树每层前缀pre<=n，共有节点数step<=n： # 如果step<=k，说明到这颗子树为止还累计不到k，去下一个兄弟节点找# 否则说明结果以这个前缀开头step += min(n + 1, next) - prepre *= 10next *= 10if step <= k:res += 1k -= stepelse:res *= 10k -= 1return res
这篇关于Leetcode 440 K-th Smallest in Lexicographical Order n叉树快速按层遍历的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
