Kth Smallest Element in a BST
你会得到一棵二叉搜索树，它以堆顺序存储在数组 root 中：根节点位于索引 0，索引 i 的子节点位于 2*i+1（左）和 2*i+2（右），-1 表示空位置。数组末尾可能有多余的 -1 项。对于每个节点，左子树中只包含较小的值，右子树中只包含较大的值。
返回树中第 k 小的值，计数从 1 开始。
函数
- rootinteger-array
- 按层序遍历的二叉搜索树，空位置用 -1 表示
- kinteger
- 要查找的位置，按从小到大的顺序排列，从 1 开始
- 返回值integer
- 树中第 k 小的值
约束条件
1 ≤ root.length ≤ 32767- 每个
root[i]都是-1或满足0 ≤ root[i] ≤ 105的值。 root[0]永远不会是-1，所以这棵树至少有一个节点。- 最后一个节点之后，数组末尾可能还有额外的
-1条目。 - 空位的两个子节点也都是空的，且深度最多为
14。 - 这个排序规则适用于每个节点，因此不会有重复值。
1 ≤ k ≤树中的节点数。
示例
- 输入
- root = [41, 17, 65, 6, 29, -1, 90, -1, -1, 22]k = 4
- 输出
- 29
- 解释
- 按升序排列，这些值是
6, 17, 22, 29, 41, 65, 90，第四个值是29。它是根节点左子树中四个值里最大的。
- 输入
- root = [12, 5, -1, 2, 9, -1, -1, -1, -1, 7, -1, -1, -1, -1, -1]k = 1
- 输出
- 2
- 解释
- 沿着一直向左延伸的路径，最小值是
12、5、2。9下面的7和-1填充值不会改变这一点。
进阶
如果树经常变化，而且你需要多次查询第 k 小的值，每个节点可以存储什么信息，让每次查询都只需 O(h)？
提示
逐个打开提示，每个都会多透露一点。
以哪种方式遍历二叉搜索树，可以按从小到大的顺序列出其中的值？
先访问左子树，再访问节点，最后访问右子树，就能得到排序后的顺序。遍历得到的第
k个值就是答案，所以你可以在那里停止。使用栈。从当前节点开始，向左子节点移动时将节点入栈。弹出栈顶并计数；在第
k次弹出时停止。否则，移动到弹出节点的右子节点2*i+2，然后重复。
题解
中序遍历（左子树、节点、右子树）会按升序读取二叉搜索树中的值，因此它访问到的第 k 个值就是答案。用自己的栈执行遍历，并在此处停止，无需排序。
收集所有值并排序
思路
忽略树的形状：保留每个不等于 -1 的条目，排序，然后返回位置 k-1 上的值。对于第一个示例，排序后的列表是 6, 17, 22, 29, 41, 65, 90，位置 3 上的值是 29。
无论树是否有序，这种方法都适用。但这也是它的代价：它忽略了树已有的顺序，排序需要花费 O(n log n)，复制则需要 O(n) 的内存。
算法
- 收集
root中所有不等于-1的条目。 - 按升序对收集到的值排序。
- 返回位置
k-1处的值。
def kthSmallest(root, k):
values = [v for v in root if v != -1] # every node, in any order
values.sort()
return values[k - 1]中序遍历并放入列表
思路
每个节点的左子树只包含更小的值，右子树只包含更大的值。先访问左子树，再访问节点，最后访问右子树，并在每个子树中执行相同的操作：每个节点都排在所有更小值之后、所有更大值之前，因此输出是有序的。在第一个示例中，遍历结果为 6, 17, 22, 29, 41, 65, 90。
一次遍历就能替代排序：时间复杂度为 O(n)，列表需要 O(n) 的空间。即使 k = 1，答案就在最左侧路径的末尾，它仍然会访问整棵树。
算法
- 编写
inorder(i)：遇到空位置（超出末尾或为-1）时返回。 - 否则，调用
inorder(2*i+1)，将root[i]添加到列表中，然后调用inorder(2*i+2)。 - 调用
inorder(0)。 - 返回列表中位置
k-1处的项。
def kthSmallest(root, k):
n = len(root)
values = []
def inorder(i):
if i >= n or root[i] == -1:
return
inorder(2 * i + 1) # smaller values first
values.append(root[i])
inorder(2 * i + 2) # then larger ones
inorder(0)
return values[k - 1] # values is sorted在第 k 个元素处停止的迭代式中序遍历
思路
显式栈可以让你在遍历过程中途停止。尽可能向左走，并将每个节点压入栈中。栈顶的节点是尚未计数的最小值，因为更小的值都在它的左子树中，而左子树为空或其中的值已经计数。弹出并计数后，接下来按排序顺序访问它的右子树。
在第一个示例中，对于 k = 4：压入 41、17、6。弹出 6，然后弹出 17，接着转到它的右子节点：压入 29 和 22。弹出 22，然后弹出 29，这就是第 4 个值。遍历不会触及 65 或 90。
栈中最多保存每一层的一个节点，因此空间复杂度为 O(h)。遍历先向下走一次，然后弹出 k 次：时间复杂度为 O(h + k)。
算法
- 从一个空栈开始，并设置
i = 0。 - 当
i是一个实际节点时，将它入栈，并移动到2*i+1。 - 将栈顶元素弹出并赋给
i，然后将k减去1。 - 如果此时
k为0，则返回root[i]。 - 否则，移动到
2*i+2，并回到第 2 步。
def kthSmallest(root, k):
n = len(root)
stack = [] # nodes whose left side is being visited, deepest on top
i = 0
while True:
while i < n and root[i] != -1: # go as far left as you can
stack.append(i)
i = 2 * i + 1
i = stack.pop() # the smallest value not counted yet
k -= 1
if k == 0:
return root[i]
i = 2 * i + 2 # then everything in its right subtree
易错点和边界情况
- 按索引顺序读取数组。层序并不是排序后的顺序：第一个示例以
41, 17, 65开头。 k的位置偏移了 1。计数从1开始：返回列表中的第k-1个位置，并在计数达到k时停止遍历。- 弹出节点后跳过右子树。在第二个示例中，
9和7位于5的右子树中，遍历时永远不会计入它们。 - 把缺失的子节点当成真实节点。当子节点的索引超出数组末尾或对应位置的值为
-1时，该子节点为空：22位于索引9，因此它的子节点19和20超出了数组末尾。 - Lua 和 R 数组的索引从 1 开始。节点索引仍使用从 0 开始的方式，以便计算
2*i+1，读取时使用root[i + 1]。
常见问题3
在二叉搜索树中查找第 k 小元素的时间复杂度是多少？
对于深度为 h 的树，迭代式中序遍历需要 O(h + k) 时间和 O(h) 额外空间。最坏情况下，当 k = n 或树的形状像一条路径时，复杂度为 O(n)。
如何在 BST 中查找第 k 大的元素？
按相反的顺序遍历：先遍历右子树，再遍历节点，最后遍历左子树。这样列出的值会按递减顺序排列。尽可能向右遍历，同时将节点入栈；弹出节点并计数后，转到左子节点。第 k 次弹出的节点就是第 k 大的节点。
如何在第 k 个值处停止递归的中序遍历？
在递归外部维护一个计数器，从 k 开始。节点的左子树返回后，将计数器减去 1；当计数器达到 0 时，记录该节点的值。每次调用后，如果已记录答案，就立即返回。这样，递归版本的复杂度与栈版本相同：时间复杂度为 O(h + k)，空间复杂度为 O(h)。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def kthSmallest(root, k):
# 在这里编写代码测试 #1
测试 #2
参数
root = [41, 17, 65, 6, 29, -1, 90, -1, -1, 22] k = 4
预期输出
29