系列文章：

算法题目解析：从一道题目看动态规划

Leetcode 题目解析：274. H 指数

Leetcode 题目解析：279. 完全平方数

Leetcode 题目解析：287. 寻找重复数

一 摘要

Top K 问题，也是一道面试中常见的算法题。大部分同学比较熟悉的可能是数组中的 Top K 元素查找，很容易想到的解决方法有堆排序、基于二分的方法。

不过随着现在内卷程度的不断提升，基础的 Top K 问题应该不足以难倒大家，所以涌现出很多 Top K 问题的变体，例如230题：二叉树中第K小的元素，17.09. 第 k 个数，440. 字典序的第K小数字等等，可以看到是 Top K 问题的系列。这里先以 230 题作为入手，深究一下 Top K 问题的解法。

二 题目描述与示例

2.1 描述

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。

2.2 示例

输入：root = [3,1,4,null,2], k = 1 输出：1

三 题目解析

3.1 描述解析

从题目看，可以简单理解为还是数组中的第 K 个最小元素，所以理论上也是可以用通用的方法来解决的。但因为是二叉搜索树，说明已经具备了排序结构，所以通用的方法必然不会是最优解。因此，必须考虑使用二叉搜索树结构的方法。

3.2 示例解析

这里用的是 leetcode 的第一个示例，也就是取最小的第 1 个元素。根据二叉搜索树的结构和使用方式，左侧节点小于根节点，右侧节点数据大于根节点，根据这个特性，从根节点一直向左搜索即可，直到找到某个节点，没有左子树，那么这个节点的值就是最小值。

示例中输入是给的数组形式，但实际上我们在写方法时，参数是 TreeNode，也就是二叉搜索树的根节点。所以在写测试用例时，需要先把数组转成二叉搜索树，并把根节点作为输入。通过 leetcode 给出的两个示例，尤其是示例二的输入：[5,3,6,2,4,null,null,1]，可见是层次遍历的结果，这里需要做到正确转换。

3.3 二叉搜索树的特性

先回顾一下二茬搜索树的特性：

• 结点的左子树只包含小于当前结点的数。

• 结点的右子树只包含大于当前结点的数。

• 所有左子树和右子树自身必须也是二叉搜索树。

另外还有重要的一点，当我们对二叉搜索树进行中序遍历时，得到的数组就是升序数组，由此，遍历到第 k 个元素时，就找到了目标值。

TreeNode 的定义：

public class TreeNode {    public int val;    public TreeNode left;    public TreeNode right;
    public TreeNode(int val){        this.val = val;    }}

3.4 解法一 中序遍历

/** * 输入：二叉搜索树根节点，参数：k * @param root * @param k * @return */public int topKSearch(TreeNode root, int k) {    Deque<TreeNode> stack = new ArrayDeque<>();    while (root != null || !stack.isEmpty()) {        while (root != null) {            stack.push(root);            root = root.left;        }        root = stack.pop();        --k;        if (k == 0) {            break;        }        root = root.right;    }    return root.val;}

复杂度分析：

1. 时间复杂度：O(H+k)，其中 H 是树的高度。在开始遍历之前，我们需要 O(H) 到达叶结点。当树是平衡树时，时间复杂度取得最小值 O(logN+k)；当树是线性树（树中每个结点都只有一个子结点或没有子结点）时，时间复杂度取得最大值 O(N+k)。

2. 空间复杂度：O(H)，栈中最多需要存储 H 个元素。当树是平衡树时，空间复杂度取得最小值 O(logN)；当树是线性树时，空间复杂度取得最大值 O(N)。