给定一个二叉搜索树（BST）和一个正整数k，在二叉搜索树中找到第k个最大元素。 例如，在下面的BST中，如果k=3，则输出应为14，如果k=5，则输出应为10。
null
![图片[1]-当不允许修改BST时，BST中的第K个最大元素-yiteyi-C++库](https://media.geeksforgeeks.org/wp-content/cdn-uploads/BST.gif)
在本文中，我们讨论了两种方法 这 邮递方法1需要O（n）时间。方法2需要O（h）时间，其中h是BST的高度，但需要增加BST（用每个节点存储左子树中的节点数）。 我们能在优于O（n）的时间内找到k个最大元素而不增加吗？
方法：
- 其思想是按顺序反向遍历BST。记录访问的节点数。
- 反向顺序遍历按降序遍历所有节点，即访问右侧节点，然后居中，然后向左，并继续递归遍历节点。
- 在进行遍历时，请跟踪到目前为止访问的节点数。
- 当计数等于k时，停止遍历并打印密钥。
C++
// C++ program to find k'th largest element in BST #include<bits/stdc++.h> using namespace std; struct Node { int key; Node *left, *right; }; // A utility function to create a new BST node Node *newNode( int item) { Node *temp = new Node; temp->key = item; temp->left = temp->right = NULL; return temp; } // A function to find k'th largest element in a given tree. void kthLargestUtil(Node *root, int k, int &c) { // Base cases, the second condition is important to // avoid unnecessary recursive calls if (root == NULL || c >= k) return ; // Follow reverse inorder traversal so that the // largest element is visited first kthLargestUtil(root->right, k, c); // Increment count of visited nodes c++; // If c becomes k now, then this is the k'th largest if (c == k) { cout << "K'th largest element is " << root->key << endl; return ; } // Recur for left subtree kthLargestUtil(root->left, k, c); } // Function to find k'th largest element void kthLargest(Node *root, int k) { // Initialize count of nodes visited as 0 int c = 0; // Note that c is passed by reference kthLargestUtil(root, k, c); } /* A utility function to insert a new node with given key in BST */ Node* insert(Node* node, int key) { /* If the tree is empty, return a new node */ if (node == NULL) return newNode(key); /* Otherwise, recur down the tree */ if (key < node->key) node->left = insert(node->left, key); else if (key > node->key) node->right = insert(node->right, key); /* return the (unchanged) node pointer */ return node; } // Driver Program to test above functions int main() { /* Let us create following BST 50 / 30 70 / / 20 40 60 80 */ Node *root = NULL; root = insert(root, 50); insert(root, 30); insert(root, 20); insert(root, 40); insert(root, 70); insert(root, 60); insert(root, 80); int c = 0; for ( int k=1; k<=7; k++) kthLargest(root, k); return 0; } |
JAVA
// Java code to find k'th largest element in BST // A binary tree node class Node { int data; Node left, right; Node( int d) { data = d; left = right = null ; } } class BinarySearchTree { // Root of BST Node root; // Constructor BinarySearchTree() { root = null ; } // function to insert nodes public void insert( int data) { this .root = this .insertRec( this .root, data); } /* A utility function to insert a new node with given key in BST */ Node insertRec(Node node, int data) { /* If the tree is empty, return a new node */ if (node == null ) { this .root = new Node(data); return this .root; } if (data == node.data) { return node; } /* Otherwise, recur down the tree */ if (data < node.data) { node.left = this .insertRec(node.left, data); } else { node.right = this .insertRec(node.right, data); } return node; } // class that stores the value of count public class count { int c = 0 ; } // utility function to find kth largest no in // a given tree void kthLargestUtil(Node node, int k, count C) { // Base cases, the second condition is important to // avoid unnecessary recursive calls if (node == null || C.c >= k) return ; // Follow reverse inorder traversal so that the // largest element is visited first this .kthLargestUtil(node.right, k, C); // Increment count of visited nodes C.c++; // If c becomes k now, then this is the k'th largest if (C.c == k) { System.out.println(k + "th largest element is " + node.data); return ; } // Recur for left subtree this .kthLargestUtil(node.left, k, C); } // Method to find the kth largest no in given BST void kthLargest( int k) { count c = new count(); // object of class count this .kthLargestUtil( this .root, k, c); } // Driver function public static void main(String[] args) { BinarySearchTree tree = new BinarySearchTree(); /* Let us create following BST 50 / 30 70 / / 20 40 60 80 */ tree.insert( 50 ); tree.insert( 30 ); tree.insert( 20 ); tree.insert( 40 ); tree.insert( 70 ); tree.insert( 60 ); tree.insert( 80 ); for ( int i = 1 ; i <= 7 ; i++) { tree.kthLargest(i); } } } // This code is contributed by Kamal Rawal |
Python3
# Python3 program to find k'th largest # element in BST class Node: # Constructor to create a new node def __init__( self , data): self .key = data self .left = None self .right = None # A function to find k'th largest # element in a given tree. def kthLargestUtil(root, k, c): # Base cases, the second condition # is important to avoid unnecessary # recursive calls if root = = None or c[ 0 ] > = k: return # Follow reverse inorder traversal # so that the largest element is # visited first kthLargestUtil(root.right, k, c) # Increment count of visited nodes c[ 0 ] + = 1 # If c becomes k now, then this is # the k'th largest if c[ 0 ] = = k: print ( "K'th largest element is" , root.key) return # Recur for left subtree kthLargestUtil(root.left, k, c) # Function to find k'th largest element def kthLargest(root, k): # Initialize count of nodes # visited as 0 c = [ 0 ] # Note that c is passed by reference kthLargestUtil(root, k, c) # A utility function to insert a new # node with given key in BST */ def insert(node, key): # If the tree is empty, # return a new node if node = = None : return Node(key) # Otherwise, recur down the tree if key < node.key: node.left = insert(node.left, key) elif key > node.key: node.right = insert(node.right, key) # return the (unchanged) node pointer return node # Driver Code if __name__ = = '__main__' : # Let us create following BST # 50 # / # 30 70 # / / # 20 40 60 80 */ root = None root = insert(root, 50 ) insert(root, 30 ) insert(root, 20 ) insert(root, 40 ) insert(root, 70 ) insert(root, 60 ) insert(root, 80 ) for k in range ( 1 , 8 ): kthLargest(root, k) # This code is contributed by PranchalK |
C#
using System; // C# code to find k'th largest element in BST // A binary tree node public class Node { public int data; public Node left, right; public Node( int d) { data = d; left = right = null ; } } public class BinarySearchTree { // Root of BST public Node root; // Constructor public BinarySearchTree() { root = null ; } // function to insert nodes public virtual void insert( int data) { this .root = this .insertRec( this .root, data); } /* A utility function to insert a new node with given key in BST */ public virtual Node insertRec(Node node, int data) { /* If the tree is empty, return a new node */ if (node == null ) { this .root = new Node(data); return this .root; } if (data == node.data) { return node; } /* Otherwise, recur down the tree */ if (data < node.data) { node.left = this .insertRec(node.left, data); } else { node.right = this .insertRec(node.right, data); } return node; } // class that stores the value of count public class count { private readonly BinarySearchTree outerInstance; public count(BinarySearchTree outerInstance) { this .outerInstance = outerInstance; } internal int c = 0; } // utility function to find kth largest no in // a given tree public virtual void kthLargestUtil(Node node, int k, count C) { // Base cases, the second condition is important to // avoid unnecessary recursive calls if (node == null || C.c >= k) { return ; } // Follow reverse inorder traversal so that the // largest element is visited first this .kthLargestUtil(node.right, k, C); // Increment count of visited nodes C.c++; // If c becomes k now, then this is the k'th largest if (C.c == k) { Console.WriteLine(k + "th largest element is " + node.data); return ; } // Recur for left subtree this .kthLargestUtil(node.left, k, C); } // Method to find the kth largest no in given BST public virtual void kthLargest( int k) { count c = new count( this ); // object of class count this .kthLargestUtil( this .root, k, c); } // Driver function public static void Main( string [] args) { BinarySearchTree tree = new BinarySearchTree(); /* Let us create following BST 50 / 30 70 / / 20 40 60 80 */ tree.insert(50); tree.insert(30); tree.insert(20); tree.insert(40); tree.insert(70); tree.insert(60); tree.insert(80); for ( int i = 1; i <= 7; i++) { tree.kthLargest(i); } } } // This code is contributed by Shrikant13 |
Javascript
<script> // javascript code to find k'th largest element in BST // A binary tree node class Node { constructor(d) { this .data = d; this .left = this .right = null ; } } // Root of BST var root = null ; // Constructor // function to insert nodes function insert(data) { this .root = this .insertRec( this .root, data); } /* A utility function to insert a new node with given key in BST */ function insertRec( node , data) { /* If the tree is empty, return a new node */ if (node == null ) { this .root = new Node(data); return this .root; } if (data == node.data) { return node; } /* Otherwise, recur down the tree */ if (data < node.data) { node.left = this .insertRec(node.left, data); } else { node.right = this .insertRec(node.right, data); } return node; } // class that stores the value of count class count { constructor(){ this .c = 0;} } // utility function to find kth largest no in // a given tree function kthLargestUtil( node , k, C) { // Base cases, the second condition is important to // avoid unnecessary recursive calls if (node == null || C.c >= k) return ; // Follow reverse inorder traversal so that the // largest element is visited first this .kthLargestUtil(node.right, k, C); // Increment count of visited nodes C.c++; // If c becomes k now, then this is the k'th largest if (C.c == k) { document.write(k + "th largest element is " + node.data+ "<br/>" ); return ; } // Recur for left subtree this .kthLargestUtil(node.left, k, C); } // Method to find the kth largest no in given BST function kthLargest(k) { c = new count(); // object of class count this .kthLargestUtil( this .root, k, c); } // Driver function /* Let us create following BST 50 / 30 70 / / 20 40 60 80 */ insert(50); insert(30); insert(20); insert(40); insert(70); insert(60); insert(80); for (i = 1; i <= 7; i++) { kthLargest(i); } // This code contributed by gauravrajput1 </script> |
输出：
K'th largest element is 80K'th largest element is 70K'th largest element is 60K'th largest element is 50K'th largest element is 40K'th largest element is 30K'th largest element is 20
复杂性分析：
- 时间复杂性： O（h+k）。 代码首先向下遍历到最右边的节点，这需要O（h）个时间，然后在O（k）个时间内遍历k个元素。因此，总体时间复杂度为O（h+k）。
- 辅助空间： O（h）。 给定时间高度h的最大递归堆栈。
?list=PLqM7alHXFySHCXD7r1J0ky9Zg_GBB1dbk 本文由 希拉格·夏尔马 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
