Dado un árbol binario que consta de N Nodes y un número entero positivo K , la tarea es encontrar el número K -ésimo más grande en el árbol dado.
Ejemplos:
Entrada: K = 3
1
/ \
2 3
/ \ / \
4 5 6 7
Salida: 5
Explicación: El tercer elemento más grande en el árbol binario dado es 5.Entrada: K = 1
1
/ \
2 3
Salida: 1
Explicación: El primer elemento más grande en el árbol binario dado es 1.
Enfoque ingenuo: aplane el árbol binario dado y luego ordene la array. Imprima ahora el K-ésimo número más grande de esta array ordenada.
Enfoque eficiente: el enfoque anterior se puede hacer eficiente almacenando todos los elementos del árbol en una cola de prioridad , ya que los elementos se almacenan según el orden de prioridad, que es ascendente de forma predeterminada. Aunque la complejidad seguirá siendo la misma que en el enfoque anterior, aquí podemos evitar el paso de clasificación adicional.
Simplemente imprima el K -ésimo elemento más grande en la cola de prioridad .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Struct binary tree node
struct Node {
int data;
Node *left, *right;
};
// Function to create a new node of
// the tree
Node* newNode(int data)
{
Node* temp = new Node();
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
// Utility function to find the Kth
// largest element in the given tree
int findKthLargest(priority_queue<int,
vector<int> >& pq,
int k)
{
// Loop until priority queue is not
// empty and K greater than 0
while (--k && !pq.empty()) {
pq.pop();
}
// If PQ is not empty then return
// the top element
if (!pq.empty()) {
return pq.top();
}
// Otherwise, return -1
return -1;
}
// Function to traverse the given
// binary tree
void traverse(
Node* root, priority_queue<int,
vector<int> >& pq)
{
if (!root) {
return;
}
// Pushing values in binary tree
pq.push(root->data);
// Left and Right Recursive Call
traverse(root->left, pq);
traverse(root->right, pq);
}
// Function to find the Kth largest
// element in the given tree
void findKthLargestTree(Node* root, int K)
{
// Stores all elements tree in PQ
priority_queue<int, vector<int> > pq;
// Function Call
traverse(root, pq);
// Function Call
cout << findKthLargest(pq, K);
}
// Driver Code
int main()
{
// Given Input
Node* root = newNode(1);
root->left = newNode(2);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right = newNode(3);
root->right->right = newNode(7);
root->right->left = newNode(6);
int K = 3;
findKthLargestTree(root, K);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
public class Main
{
// Struct binary tree node
static class Node
{
int data;
Node left;
Node right;
}
// Function to create new node of the tree
static Node newNode(int data)
{
Node temp = new Node();
temp.data = data;
temp.left = null;
temp.right = null;
return temp;
}
// Stores all elements tree in PQ
static Vector<Integer> pq = new Vector<Integer>();
// Utility function to find the Kth
// largest element in the given tree
static int findKthLargest(int k)
{
// Loop until priority queue is not
// empty and K greater than 0
--k;
while (k > 0 && pq.size() > 0) {
pq.remove(0);
--k;
}
// If PQ is not empty then return
// the top element
if (pq.size() > 0) {
return pq.get(0);
}
// Otherwise, return -1
return -1;
}
// Function to traverse the given
// binary tree
static void traverse(Node root)
{
if (root == null) {
return;
}
// Pushing values in binary tree
pq.add(root.data);
Collections.sort(pq);
Collections.reverse(pq);
// Left and Right Recursive Call
traverse(root.left);
traverse(root.right);
}
// Function to find the Kth largest
// element in the given tree
static void findKthLargestTree(Node root, int K)
{
// Function Call
traverse(root);
// Function Call
System.out.print(findKthLargest(K));
}
// Driver code
public static void main(String[] args)
{
// Given Input
Node root = newNode(1);
root.left = newNode(2);
root.left.left = newNode(4);
root.left.right = newNode(5);
root.right = newNode(3);
root.right.right = newNode(7);
root.right.left = newNode(6);
int K = 3;
findKthLargestTree(root, K);
}
}
// This code is contributed by divyesh07.
Python3
# Python3 program for the above approach class Node: # Struct binary tree node def __init__(self, data): self.data = data self.left = None self.right = None # Stores all elements tree in PQ pq = [] # Utility function to find the Kth # largest element in the given tree def findKthLargest(k): # Loop until priority queue is not # empty and K greater than 0 k-=1 while (k > 0 and len(pq) > 0): pq.pop(0) k-=1 # If PQ is not empty then return # the top element if len(pq) > 0: return pq[0] # Otherwise, return -1 return -1 # Function to traverse the given # binary tree def traverse(root): if (root == None): return # Pushing values in binary tree pq.append(root.data) pq.sort() pq.reverse() # Left and Right Recursive Call traverse(root.left) traverse(root.right) # Function to find the Kth largest # element in the given tree def findKthLargestTree(root, K): # Function Call traverse(root); # Function Call print(findKthLargest(K)) # Given Input root = Node(1) root.left = Node(2) root.left.left = Node(4) root.left.right = Node(5) root.right = Node(3) root.right.right = Node(7) root.right.left = Node(6) K = 3 findKthLargestTree(root, K) # This code is contributed by mukesh07.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG {
// Struct binary tree node
class Node
{
public int data;
public Node left, right;
};
// Function to create a new node of the tree
static Node newNode(int data)
{
Node temp = new Node();
temp.data = data;
temp.left = null;
temp.right = null;
return temp;
}
// Stores all elements tree in PQ
static List<int> pq = new List<int>();
// Utility function to find the Kth
// largest element in the given tree
static int findKthLargest(int k)
{
// Loop until priority queue is not
// empty and K greater than 0
--k;
while (k > 0 && pq.Count > 0) {
pq.RemoveAt(0);
--k;
}
// If PQ is not empty then return
// the top element
if (pq.Count > 0) {
return pq[0];
}
// Otherwise, return -1
return -1;
}
// Function to traverse the given
// binary tree
static void traverse(Node root)
{
if (root == null) {
return;
}
// Pushing values in binary tree
pq.Add(root.data);
pq.Sort();
pq.Reverse();
// Left and Right Recursive Call
traverse(root.left);
traverse(root.right);
}
// Function to find the Kth largest
// element in the given tree
static void findKthLargestTree(Node root, int K)
{
// Function Call
traverse(root);
// Function Call
Console.Write(findKthLargest(K));
}
static void Main() {
// Given Input
Node root = newNode(1);
root.left = newNode(2);
root.left.left = newNode(4);
root.left.right = newNode(5);
root.right = newNode(3);
root.right.right = newNode(7);
root.right.left = newNode(6);
int K = 3;
findKthLargestTree(root, K);
}
}
// This code is contributed by divyeshrabadiya07.
Javascript
<script>
// Javascript program for the above approach
// Struct binary tree node
class Node
{
constructor(data) {
this.left = null;
this.right = null;
this.data = data;
}
}
// Function to create a new node of the tree
function newNode(data)
{
let temp = new Node(data);
return temp;
}
// Stores all elements tree in PQ
let pq = [];
// Utility function to find the Kth
// largest element in the given tree
function findKthLargest(k)
{
// Loop until priority queue is not
// empty and K greater than 0
--k;
while (k > 0 && pq.length > 0) {
pq.shift();
--k;
}
// If PQ is not empty then return
// the top element
if (pq.length > 0) {
return pq[0];
}
// Otherwise, return -1
return -1;
}
// Function to traverse the given
// binary tree
function traverse(root)
{
if (root == null) {
return;
}
// Pushing values in binary tree
pq.push(root.data);
pq.sort(function(a, b){return a - b});
pq.reverse();
// Left and Right Recursive Call
traverse(root.left);
traverse(root.right);
}
// Function to find the Kth largest
// element in the given tree
function findKthLargestTree(root, K)
{
// Function Call
traverse(root);
// Function Call
document.write(findKthLargest(K));
}
// Given Input
let root = newNode(1);
root.left = newNode(2);
root.left.left = newNode(4);
root.left.right = newNode(5);
root.right = newNode(3);
root.right.right = newNode(7);
root.right.left = newNode(6);
let K = 3;
findKthLargestTree(root, K);
// This code is contributed by decode2207.
</script>
Producción:
5
Complejidad de Tiempo: O((N + K)log N)
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por namanaggarwal1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA