LeetCode二叉搜索树中第k小元素求解：优化方案与调试记录

最近我在刷LeetCode上的「二叉搜索树中第k小的元素」这道题，这里跟大家分享下我的解题过程和两种不同的解法：

题目要求：给定一棵二叉搜索树（BST），找出其中第k小的元素并返回其值。

1. 初始O(n)时间与空间复杂度解法 #

一开始我想到的是利用BST的核心特性——中序遍历结果是升序序列。具体思路很直接：

• 先通过递归中序遍历整棵树，把所有节点的值存入一个数组
• 因为数组是升序的，直接返回数组中索引为k-1的元素即可

这种解法的时间和空间复杂度都是O(n)，毕竟要遍历所有节点还要存储所有值。给大家贴个Python实现的代码：

def kthSmallest(root, k):
    res = []
    def inorder(node):
        if not node:
            return
        inorder(node.left)
        res.append(node.val)
        inorder(node.right)
    inorder(root)
    return res[k-1]

2. 优化后的高效解法 #

后来我查了些资料，发现可以进一步优化——不用把所有节点值都存起来，而是在中序遍历的过程中实时计数，当计数到k的时候直接返回当前节点的值，这样就能提前终止遍历，省不少空间和时间。

优化后的思路：

• 同样用中序遍历，但增加一个计数器
• 每遍历到一个节点（左子树遍历完后），计数器加1
• 当计数器等于k时，记录当前节点的值并立刻终止所有递归
• 空间复杂度降到了O(h)（h是树的高度，也就是递归栈的深度），最坏情况时间还是O(n)，但平均情况下效率更高

代码实现如下：

def kthSmallest(root, k):
    count = 0
    result = None
    def inorder(node):
        nonlocal count, result
        # 如果已经找到结果，直接返回，避免多余遍历
        if not node or result is not None:
            return
        inorder(node.left)
        count += 1
        if count == k:
            result = node.val
            return
        inorder(node.right)
    inorder(root)
    return result

调试过程 #

为了彻底搞懂这个优化解法的执行流程，我在代码的几个关键位置设置了断点：

• 进入左子树递归的行
• 计数器递增的行
• 判断计数器是否等于k的分支行
• 进入右子树递归的行
  通过逐步调试，我清晰看到了中序遍历的顺序，以及当计数到k时如何提前终止递归、返回结果的整个过程，对这个解法的理解更透彻了。

内容的提问来源于stack exchange，提问作者Ganpat