✅给定一个二叉搜索树，请找出其中第k小的元素

典型回答

在二叉搜索树中查找第k小的元素，可以利用二叉搜索树的一个重要性质：二叉搜索树的中序遍历序列是有序的。因此，可以通过对二叉搜索树进行中序遍历并计数来找到第k小的元素。

---

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    private int count = 0; // 用于计数已遍历的节点
    private int result = Integer.MIN_VALUE; // 存储第k小的元素

    public int kthSmallest(TreeNode root, int k) {
        inOrderTraverse(root, k);
        return result;
    }

    private void inOrderTraverse(TreeNode node, int k) {
        if (node == null) return;

        // 先遍历左子树
        inOrderTraverse(node.left, k);

        // 访问节点
        count++;
        if (count == k) {
            result = node.val;
            return; // 找到第k小的元素后返回
        }

        // 遍历右子树
        inOrderTraverse(node.right, k);
    }
}

这段代码首先定义了一个辅助方法inOrderTraverse，用于对二叉搜索树进行中序遍历。在遍历过程中，使用一个计数器count来记录当前已经遍历过的节点数量。当count等于k时，表示当前节点就是第k小的元素，此时将当前节点的值赋给result并返回。

在主方法kthSmallest中，调用inOrderTraverse方法并传入根节点和k。中序遍历完成后，result就是第k小的元素。

原文: https://www.yuque.com/hollis666/xkm7k3/imwa0dbaw3v1vrb1