Dado un árbol binario completo donde el valor de cada Node es el mismo que el valor mínimo entre sus hijos, la tarea es encontrar el segundo valor único mínimo del árbol.
Ejemplos:
Entrada: árbol:
Ejemplo de enunciado del problema
Salida: 5
Explicación: Todos los valores únicos presentes en el árbol son 2, 5 y 7.
El segundo más pequeño es 5.Entrada: árbol:
Otro ejemplo de enunciado de un problema
Salida: -1
Explicación: Todos los números presentes en el árbol son iguales.
No hay otro valor excepto 2, por lo que el segundo más pequeño no es posible.
Enfoque ingenuo: El enfoque básico para resolver el problema se basa en la idea:
Almacene todos los valores únicos en una array y ordene la array. Luego encuentre el segundo mínimo de la array.
Siga el siguiente paso para entender el enfoque más claramente:
- Recorra el árbol y almacene todos los valores en una array.
- Ordenar la array.
- Iterar sobre la array y encontrar el primer elemento de la array que no sea igual al elemento mínimo de la array (es decir, el presente en el índice 0). Si tal elemento no está presente, devuelve -1.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code to implement the above approach
#include <bits/stdc++.h>
using namespace std;
// Structure of a tree node
struct Node {
int data;
struct Node* left;
struct Node* right;
Node(int val)
{
data = val;
left = NULL;
right = NULL;
}
};
// Initialize a vector
vector<int> ans;
// Traversing the tree by using inorder
// traversal
void inorderTraversal(Node* root)
{
if (root != NULL) {
inorderTraversal(root->left);
ans.push_back(root->data);
inorderTraversal(root->right);
}
}
// Function to find the second minimum element
int findSecondMinimumValue(Node* root)
{
inorderTraversal(root);
// Sorting the array element
sort(ans.begin(), ans.end());
// Traversing and array and checking
// the second minimum element
for (int i = 0; i < ans.size() - 1; i++)
if (ans[i] != ans[i + 1])
return ans[i + 1];
return -1;
}
// Driver code
int main()
{
// Creating the tree
// 2
// / \
// 2 5
// / \
// 5 7
struct Node* root = new Node(2);
root->left = new Node(2);
root->right = new Node(5);
root->right->left = new Node(5);
root->right->right = new Node(7);
// Function call
int SecondMinimumValue
= findSecondMinimumValue(root);
cout << SecondMinimumValue << endl;
return 0;
}
Java
// JAVA code to implement the above approach
import java.util.*;
class GFG
{
// Structure of a tree node
public static class Node {
int data;
Node left;
Node right;
Node(int val) { this.data = val; }
}
// Initialize a vector
public static ArrayList<Integer> ans
= new ArrayList<Integer>();
// Traversing the tree by using inorder
// traversal
public static void inorderTraversal(Node root)
{
if (root != null) {
inorderTraversal(root.left);
ans.add(root.data);
inorderTraversal(root.right);
}
}
// Function to find the second minimum element
public static int findSecondMinimumValue(Node root)
{
inorderTraversal(root);
// Sorting the array element
Collections.sort(ans);
// Traversing and array and checking
// the second minimum element
for (int i = 0; i < ans.size() - 1; i++)
if (ans.get(i) != ans.get(i + 1))
return ans.get(i + 1);
return -1;
}
// Driver code
public static void main(String[] args)
{
// Creating the tree
// 2
// / \
// 2 5
// / \
// 5 7
Node root = new Node(2);
root.left = new Node(2);
root.right = new Node(5);
root.right.left = new Node(5);
root.right.right = new Node(7);
// Function call
int SecondMinimumValue
= findSecondMinimumValue(root);
System.out.println(SecondMinimumValue);
}
}
// This code is contributed by Taranpreet
Python3
# Python3 code for the above approach # class to create a tree node class Node: def __init__(self, d): self.data = d self.left = None self.right = None # Initialize a list ans = [] # Traversing the tree by using inorder # traversal def inorderTraversal(root) : if (root != None) : inorderTraversal(root.left) ans.append(root.data) inorderTraversal(root.right) # Function to find the second minimum element def findSecondMinimumValue(root) : inorderTraversal(root) # Sorting the array element ans.sort() # Traversing and array and checking # the second minimum element for i in range(0,len(ans)-1) : if (ans[i] != ans[i + 1]) : return ans[i + 1] return -1 # Driver Code if __name__ == '__main__': # Driver code # Creating the tree # 2 # / \ # 2 5 # / \ # 5 7 root = Node(2) root.left = Node(2) root.right = Node(5) root.right.left = Node(5) root.right.right = Node(7) # Function call SecondMinimumValue = findSecondMinimumValue(root) print(SecondMinimumValue) # This code is contributed by jana_sayantan.
Javascript
<script>
// JavaScript code for the above approach
// Structure of a tree node
class Node {
constructor(val) {
this.data = val;
this.left = null;
this.right = null;
}
};
// Initialize a vector
let ans = [];
// Traversing the tree by using inorder
// traversal
function inorderTraversal(root) {
if (root != null) {
inorderTraversal(root.left);
ans.push(root.data);
inorderTraversal(root.right);
}
}
// Function to find the second minimum element
function findSecondMinimumValue(root) {
inorderTraversal(root);
// Sorting the array element
ans.sort();
// Traversing and array and checking
// the second minimum element
for (let i = 0; i < ans.length - 1; i++)
if (ans[i] != ans[i + 1])
return ans[i + 1];
return -1;
}
// Driver code
// Creating the tree
// 2
// / \
// 2 5
// / \
// 5 7
let root = new Node(2);
root.left = new Node(2);
root.right = new Node(5);
root.right.left = new Node(5);
root.right.right = new Node(7);
// Function call
let SecondMinimumValue
= findSecondMinimumValue(root);
document.write(SecondMinimumValue + '<br>');
// This code is contributed by Potta Lokesh
</script>
C#
// C# code to implement the above approach
using System;
using System.Collections.Generic;
public class GFG
{
// Structure of a tree node
public class Node {
public int data;
public Node left;
public Node right;
public Node(int val) { this.data = val; }
}
// Initialize a vector
public static List<int> ans
= new List<int>();
// Traversing the tree by using inorder
// traversal
public static void inorderTraversal(Node root)
{
if (root != null) {
inorderTraversal(root.left);
ans.Add(root.data);
inorderTraversal(root.right);
}
}
// Function to find the second minimum element
public static int findSecondMinimumValue(Node root)
{
inorderTraversal(root);
// Sorting the array element
ans.Sort();
// Traversing and array and checking
// the second minimum element
for (int i = 0; i < ans.Count - 1; i++)
if (ans[i] != ans[i + 1])
return ans[i + 1];
return -1;
}
// Driver code
public static void Main(String[] args)
{
// Creating the tree
// 2
// / \
// 2 5
// / \
// 5 7
Node root = new Node(2);
root.left = new Node(2);
root.right = new Node(5);
root.right.left = new Node(5);
root.right.right = new Node(7);
// Function call
int SecondMinimumValue
= findSecondMinimumValue(root);
Console.WriteLine(SecondMinimumValue);
}
}
// This code contributed by shikhasingrajput
Producción
5
Complejidad temporal: O(N * logN)
Espacio auxiliar: O(N)
Enfoque eficiente: el problema se puede resolver de manera eficiente utilizando la siguiente observación:
El Node raíz del árbol contiene el mínimo entre todos los Nodes.
Si el valor de todos los Nodes con valor mínimo se reemplaza por otros números arbitrarios fuera del rango de valores del árbol y se mantiene la propiedad del árbol, entonces el Node raíz tendrá el valor mínimo actual, que en realidad es el segundo mínimo del árbol dado. .
La observación anterior se puede implementar usando recursividad . Siga el enfoque mencionado a continuación para implementar la idea de la observación anterior:
- Use una función recursiva para recorrer el árbol e implementar la observación.
- En cada recursión para cualquier Node:
- Encuentre cuál de sus hijos tiene el mismo valor que la raíz y llame a la siguiente recursión para ese hijo.
- Si el valor del Node actual es el mismo que el de la raíz y no tiene hijos, o ambos hijos tienen el mismo valor, reemplace su valor con -1 .
- Si el Node actual tiene hijos, reemplácelo con el mínimo de sus hijos mientras regresa de la función recursiva. (Esto reemplazará el valor con el segundo mínimo ya que el mínimo se reemplaza con -1 y -1 no se considera para verificar el mínimo).
- De esta manera, mientras se completa el recorrido, la raíz del árbol contiene el mínimo actual del árbol, que en realidad es el segundo mínimo del árbol original.
- Devuelve el valor de la raíz .
A continuación se muestra el código del enfoque anterior:
C++
// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
// Structure of a tree node
struct Node {
int data;
struct Node* left;
struct Node* right;
Node(int val)
{
data = val;
left = NULL;
right = NULL;
}
};
// Function to find the minimum value
int findSecondMinimumValue(Node* root)
{
// When the root is null
if (!root)
return -1;
// Base Condition
// When we reach the Leaf node then
// in that case we have to return -1
// as per the algorithm stated in
// the above statement
if (!root->left && !root->right)
return -1;
// Storing the Node value of the left
// child of the Node
auto left = root->left->data;
// Storing the Node value of the right
// child of the Node
auto right = root->right->data;
// Call the function recursively to the
// left sub-part of the tree if the value
// of the node value matches with its left
// child node value
if (root->data == root->left->data)
left
= findSecondMinimumValue(root->left);
// Call the function recursively to the
// right sub-part of the tree if the
// value of the node value matches with
// its right child node value
if (root->data == root->right->data)
right
= findSecondMinimumValue(root->right);
// In case if both the left and right
// child value is not equal to -1 then
// in that case return the minimum of
// them to the its parent
if (left != -1 && right != -1)
return min(left, right);
// In case if the left child's value is
// not equal to -1 BUT its right child's
// value is equal to -1 then in that case
// send the left child value to its
// parent node.
else if (left != -1)
return left;
// In case if the right child's value is
// not equal to -1 BUT its left child's
// value is equal to -1 then in that case
// send the right child value to its
// parent node.
else
return right;
}
// Driver code
int main()
{
// Creating the root node
/* 2
/ \
2 5
/ \
5 7 */
struct Node* root = new Node(2);
root->left = new Node(2);
root->right = new Node(5);
root->right->left = new Node(5);
root->right->right = new Node(7);
int SecondMinimumValue
= findSecondMinimumValue(root);
cout << SecondMinimumValue << endl;
return 0;
}
C
// C program for above approach
#include <stdio.h>
#include <stdlib.h>
// Structure of a tree node
typedef struct Node {
int data;
struct Node* left;
struct Node* right;
} Node;
Node* newNode(int data)
{
Node* new_node = (Node*)malloc(sizeof(Node));
new_node->data = data;
new_node->left = new_node->right = NULL;
return new_node;
}
// Find minimum between two numbers.
int min(int num1, int num2)
{
return (num1 > num2) ? num2 : num1;
}
// Function to find the minimum value
int findSecondMinimumValue(Node* root)
{
// When the root is null
if (!root)
return -1;
// Base Condition
// When we reach the Leaf node then
// in that case we have to return -1
// as per the algorithm stated in
// the above statement
if (!root->left && !root->right)
return -1;
// Storing the Node value of the left
// child of the Node
int left = root->left->data;
// Storing the Node value of the right
// child of the Node
int right = root->right->data;
// Call the function recursively to the
// left sub-part of the tree if the value
// of the node value matches with its left
// child node value
if (root->data == root->left->data)
left = findSecondMinimumValue(root->left);
// Call the function recursively to the
// right sub-part of the tree if the
// value of the node value matches with
// its right child node value
if (root->data == root->right->data)
right = findSecondMinimumValue(root->right);
// In case if both the left and right
// child value is not equal to -1 then
// in that case return the minimum of
// them to the its parent
if (left != -1 && right != -1)
return min(left, right);
// In case if the left child's value is
// not equal to -1 BUT its right child's
// value is equal to -1 then in that case
// send the left child value to its
// parent node.
else if (left != -1)
return left;
// In case if the right child's value is
// not equal to -1 BUT its left child's
// value is equal to -1 then in that case
// send the right child value to its
// parent node.
else
return right;
}
// Driver code
int main()
{
// Creating the root node
/* 2
/ \
2 5
/ \
5 7 */
Node* root = newNode(2);
root->left = newNode(2);
root->right = newNode(5);
root->right->left = newNode(5);
root->right->right = newNode(7);
int SecondMinimumValue = findSecondMinimumValue(root);
printf("%d\n", SecondMinimumValue);
return 0;
}
// This code is contributed by Sania Kumari Gupta
Python3
# Python program to implement above approach # Structure of a tree node class Node: def __init__(self,val): self.data = val self.left = None self.right = None # Function to find the minimum value def findSecondMinimumValue(root): # When the root is None if (root == None): return -1 # Base Condition # When we reach the Leaf node then # in that case we have to return -1 # as per the algorithm stated in # the above statement if (root.left == None and root.right == None): return -1 # Storing the Node value of the left # child of the Node left = root.left.data # Storing the Node value of the right # child of the Node right = root.right.data # Call the function recursively to the # left sub-part of the tree if the value # of the node value matches with its left # child node value if (root.data == root.left.data): left = findSecondMinimumValue(root.left) # Call the function recursively to the # right sub-part of the tree if the # value of the node value matches with # its right child node value if (root.data == root.right.data): right = findSecondMinimumValue(root.right) # In case if both the left and right # child value is not equal to -1 then # in that case return the minimum of # them to the its parent if (left != -1 and right != -1): return min(left, right) # In case if the left child's value is # not equal to -1 BUT its right child's # value is equal to -1 then in that case # send the left child value to its # parent node. elif (left != -1): return left # In case if the right child's value is # not equal to -1 BUT its left child's # value is equal to -1 then in that case # send the right child value to its # parent node. else: return right # Driver code root = Node(2) root.left = Node(2) root.right = Node(5) root.right.left = Node(5) root.right.right = Node(7) SecondMinimumValue = findSecondMinimumValue(root) print(SecondMinimumValue) # This code is contributed by shinjanpatra
Javascript
<script>
// JavaScript program to implement above approach
// Structure of a tree node
class Node {
constructor(val)
{
this.data = val;
this.left = null;
this.right = null;
}
};
// Function to find the minimum value
function findSecondMinimumValue(root)
{
// When the root is null
if (!root)
return -1;
// Base Condition
// When we reach the Leaf node then
// in that case we have to return -1
// as per the algorithm stated in
// the above statement
if (!root.left && !root.right)
return -1;
// Storing the Node value of the left
// child of the Node
let left = root.left.data;
// Storing the Node value of the right
// child of the Node
let right = root.right.data;
// Call the function recursively to the
// left sub-part of the tree if the value
// of the node value matches with its left
// child node value
if (root.data == root.left.data)
left = findSecondMinimumValue(root.left);
// Call the function recursively to the
// right sub-part of the tree if the
// value of the node value matches with
// its right child node value
if (root.data == root.right.data)
right = findSecondMinimumValue(root.right);
// In case if both the left and right
// child value is not equal to -1 then
// in that case return the minimum of
// them to the its parent
if (left != -1 && right != -1)
return Math.min(left, right);
// In case if the left child's value is
// not equal to -1 BUT its right child's
// value is equal to -1 then in that case
// send the left child value to its
// parent node.
else if (left != -1)
return left;
// In case if the right child's value is
// not equal to -1 BUT its left child's
// value is equal to -1 then in that case
// send the right child value to its
// parent node.
else
return right;
}
// Driver code
let root = new Node(2);
root.left = new Node(2);
root.right = new Node(5);
root.right.left = new Node(5);
root.right.right = new Node(7);
let SecondMinimumValue = findSecondMinimumValue(root);
document.write(SecondMinimumValue,"</br>");
// This code is contributed by shinjanpatra
</script>
Producción
5
Complejidad de Tiempo: O(H) donde H es la altura del árbol
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por adityakumar129 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA