难度: Medium
给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。
示例 1：
输入：root = [3,1,4,null,2], k = 1 输出：1
示例 2：
输入：root = [5,3,6,2,4,null,null,1], k = 3 输出：3
提示：
n 。1 <= k <= n <= 1040 <= Node.val <= 104
进阶：如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化算法？
运行时间: 60 ms
内存: 18.9 MB
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
stack = []
while root is not None or len(stack) > 0:
if root is None:
root = stack.pop()
k -= 1
if k == 0:
return root.val
root = root.right
else:
stack.append(root)
root = root.left
这个题解使用了迭代的方式进行中序遍历二叉搜索树。中序遍历二叉搜索树可以得到一个升序排列的序列，因此第k小的元素就是中序遍历序列中的第k个元素。具体做法是：用一个栈来模拟递归的过程，首先不断地将根节点的左子树压入栈中，直到左子树为空；然后弹出栈顶元素并将k减1，如果此时k等于0，说明已经找到了第k小的元素，直接返回该元素的值；否则继续遍历该元素的右子树。重复这个过程直到找到第k小的元素或遍历完整棵树。
时间复杂度: O(h+k)，其中h为树的高度
空间复杂度: O(h)，其中h为树的高度
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
stack = []
while root is not None or len(stack) > 0:
# 不断地将根节点的左子树压入栈中，直到左子树为空
if root is None:
# 弹出栈顶元素
root = stack.pop()
k -= 1
# 如果k等于0，说明已经找到了第k小的元素，直接返回该元素的值
if k == 0:
return root.val
# 继续遍历该元素的右子树
root = root.right
else:
# 将当前节点压入栈中
stack.append(root)
# 遍历当前节点的左子树
root = root.left
在二叉搜索树中，即使存在相同值的节点，中序遍历依然可以正确地按顺序访问每个节点。算法中的中序遍历会按照左-根-右的顺序访问这些节点，包括重复值节点。这意味着即便是具有相同值的节点，它们也会根据在树中的位置被逐一考虑。因此，尽管存在相同的值，第k小的元素的查找仍然是准确的，每个节点都会被按照中序顺序计算。
迭代方法相比递归方法在管理内存上有更好的控制，因为它避免了递归调用栈的开销。在递归方法中，每次函数调用都会增加调用栈的深度，而对于深度很大的树来说，这可能导致栈溢出。迭代方法通过显式使用栈来处理节点，这样可以更直观地控制栈的大小，减少因深度大而造成的内存问题。此外，迭代方法通常在理解和调试方面更为直接，尤其是在复杂的树遍历操作中。
为了优化算法以支持频繁的插入和删除操作，可以使用一些特殊的数据结构，如平衡二叉搜索树（例如AVL树或红黑树），这些树结构可以在插入和删除操作后自动保持平衡，从而保持操作的时间复杂度为O(log n)。此外，可以考虑使用Augmented Tree，其中节点增加了额外的信息，如子树的节点数量，这样可以更快地直接访问第k小的元素。还可以考虑使用Order Statistic Tree，它是一种可以直接通过节点的统计信息快速检索第k小元素的红黑树变种。
如果k大于树的节点总数，则中序遍历完成后，k仍然大于0。在当前的算法实现中，这种情况会导致函数无返回值或可能引发错误，因为算法假设k是一个有效的输入。为了处理这种边界情况，可以在遍历开始前添加代码来检查树中节点的总数，如果节点总数小于k，则直接返回一个错误或特定的值，指示输入不合理。这需要额外的时间来计算树的大小，但可以防止无效操作。