LeetCode 230：二叉搜索树中的第K小元素 — 逐步可视化追踪

Source: Dev.to

问题描述

在二叉搜索树（BST）中查找第 k 小 的元素，k 为从 1 开始计数。函数应返回所有节点按升序排序后，第 k 小节点的值。

思路

该解法使用 中序遍历 对 BST 进行遍历，天然按升序访问节点。递归先遍历左子树，处理当前节点，再遍历右子树，构建完整的已排序值列表，最后返回第 k 个元素。

复杂度

• 时间复杂度: O(n)
• 空间复杂度: O(n)

代码

class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        def inorder_traversal(node):
            if not node:
                return []

            left = inorder_traversal(node.left)
            right = inorder_traversal(node.right)

            return left + [node.val] + right

        inorder_values = inorder_traversal(root)
        return inorder_values[k - 1]

交互式可视化

打开 TraceLit — 用于 LeetCode 练习的可视化算法追踪器。