230. 二叉搜索树中第K小的元素

给定一个二叉搜索树的根节点 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 <= 10^4
• 0 <= Node.val <= 10^4

进阶：如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化算法？

中序遍历。无返回值有信息参数的DFS

class Solution {
    public int kthSmallest(TreeNode root, int k) {
        // 利用 BST 的中序遍历特性，递归寻找第 k 小的元素
        dfs(root, k);
        return res;
    }

    // 记录结果
    int res = 0;
    // 记录当前元素的排名。rank从0开始，遇见非空节点就自增，因此左下角的节点的rank是1
    int rank = 0;
    void dfs(TreeNode root, int k) {
        // 特殊条件。
        if (root == null) {
            return;
        }
        
        // 先递归遍历左子树
        dfs(root.left, k);
        // 访问当前节点
        rank++;
        // 结束条件：如果当前访问的节点排名等于 k，说明找到了第 k 小的元素。必须在中序位置执行，这样root和rank才一致。
        if (k == rank) {
            res = root.val;
            // 找到后直接返回，无需继续遍历
            return;
        }
        // 递归遍历右子树
        dfs(root.right, k);
    }
}

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

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

二分+DFS

class Solution {
    // 递归调用log n次，n是节点总数，因此时间和空间复杂度都是log n。
    // countNodes 方法的时间复杂度是O(n).
    public int kthSmallest(TreeNode root, int k) {
        int leftNodes = countNodes(root.left);
        if (leftNodes < k - 1) { // 答案存在右子树中
            return kthSmallest(root.right, k - leftNodes - 1);
        } else if (leftNodes == k - 1) {
            return root.val;
        } else {
            return kthSmallest(root.left, k);
        }
    }

    // 左神递归套路分析左右子树返回信息只需要节点数，因此无需额外定义数据结构，
    // 遍历每个节点，因此时间复杂度是O(n)，n是节点个数。空间复杂度是O(n)，即递归栈的深度。
    public int countNodes(TreeNode root) {
        // base case返回0
        if (root == null)
            return 0;
        // 递归处理左右子树并接收返回值
        int leftNodes = countNodes(root.left);
        int rightNodes = countNodes(root.right);
        // 判断分析本层递归返回值的具体值
        return leftNodes + rightNodes + 1;
    }
}

• 时间复杂度：平衡树时，$n/2+n/4+\cdots+1=O(n)$，链表时，$n-1+n-2+\cdots+1=O(n^2)$。
• 空间复杂度：平衡树时，$O(\log n)$，链表时，$O(n)$。