Unicorns VO 面试真题解析：BST 中第 K 大元素（Kth Largest Element in a Binary Search Tree）

Given a Binary Search Tree (BST) and a positive integer k, find the kth largest element in the Binary Search Tree.

For example, in the following BST, if k = 3, then the output should be 15, and if k = 5, then the output should be 4.

      10
     /  \
    4    20
   /    /  \
  2    15   40

这道题要求在二叉搜索树中找到第 k 大的节点值。由于 BST 的中序遍历会得到升序序列，因此只要改用“右 - 根 - 左”的逆中序遍历，就能按从大到小的顺序访问节点，并在访问到第 k 个元素时直接返回。这样可以避免把所有节点先存起来，时间复杂度为 O(n)，在递归或栈实现下空间复杂度通常为 O(h)，其中 h 是树高。