使用 Python 以恒定额外空间在 BST 中查找第 K 大元素

什么是二叉搜索树？

二叉搜索树是一种二叉数据结构，包含各种具有特定属性的节点，包括

• 左子树的节点小于根节点。
• 右子树的节点大于根节点。
• 树节点中每个节点的子节点都构成一个二叉搜索树。

问题陈述

我们需要找到现有二叉搜索树中的第 K 大元素。这意味着我们首先按降序排列二叉搜索树的元素；然后，我们将搜索二叉搜索树中的第 K 大元素。

让我们通过一个例子来理解问题陈述。

示例

输入

输出

14

说明

我们有一个二叉搜索树，需要搜索第 K 大的元素。我们给出的输入是 4，即 k 为 4。我们需要搜索二叉搜索树中的第 4 大元素。我们将首先按降序排列二叉搜索树的元素，然后找到第 4 大的元素。

查找 BST 中第 K 大元素的思路

查找 BST 中第 K 大元素的思路有多种。包括

1. 朴素方法

使用朴素方法，我们可以存储中序遍历，然后查找n - k + 1 元素，其中 n 是元素总数，k 是我们要搜索的元素。这种方法的空间复杂度为 O(N)，这意味着它会占用更多空间且效率低下。

因此，我们将使用一种更有效的方法来查找二叉搜索树中的第 K 大元素。

2. 反向莫里斯遍历

这种方法基于线索二叉树。线索二叉二叉树就是一个普通的二叉树，带有一条额外的线索，有助于轻松遍历树。它使用 NULL 指针，这些指针存储了用于使用这些 NULL 指针的未使用的后继节点和前驱节点（前一个和下一个节点）。

反向莫里斯遍历只是莫里斯遍历的逆序。与莫里斯遍历（我们首先访问左子树，然后访问右子树，而不使用堆栈或递归）不同，在反向莫里斯遍历中，我们将首先遍历右子树，然后遍历左子树。它具有恒定的 O(1) 额外内存消耗。这是查找二叉搜索树中第 K 大元素的最优方法。

此问题陈述的逻辑是执行反向中序遍历，该遍历默认会按降序给出列表，同时跟踪访问的节点数。当计数等于我们要搜索的元素 (k) 时，我们将打印该元素。

查找二叉搜索树中第 K 大元素的实现

代码

输出

Enter the kth element to be searched: 3
The  K-th largest Node in Binary Search Tree is :  11

说明

使用的二叉树是

我们首先将当前节点初始化为根节点。我们初始化了一个计数变量，以反向顺序遍历二叉树，检查第 K 个元素是否与当前节点匹配，并计算节点数。我们发现元素 11 是第 K 大的元素（k = 3）。