Dado un árbol de N Nodes, la tarea es encontrar el Node que tiene la máxima profundidad a partir del Node raíz, tomando el Node raíz a profundidad cero. Si hay más de 1 Node de profundidad máxima, busque el que tenga el valor más pequeño.
Ejemplos:
Input:
1
/ \
2 3
/ \
4 5
Output: 4
Explanation:
For this tree:
Height of Node 1 - 0,
Height of Node 2 - 1,
Height of Node 3 - 1,
Height of Node 4 - 2,
Height of Node 5 - 2.
Hence, the nodes whose height is
maximum are 4 and 5, out of which
4 is minimum valued.
Input:
1
/
2
/
3
Output: 3
Explanation:
For this tree:
Height of Node 1 - 0,
Height of Node 2 - 1,
Height of Node 3 - 2
Hence, the node whose height
is maximum is 3.
Acercarse:
- La idea es usar la búsqueda en profundidad primero (DFS) en el árbol y para cada Node, verifique la altura de cada Node a medida que avanzamos hacia abajo en el árbol.
- Compruebe si es el máximo hasta ahora o no y si tiene una altura igual al valor máximo, entonces es el Node de valor mínimo o no.
- En caso afirmativo, actualice la altura máxima hasta el momento y el valor del Node en consecuencia.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of for
// the above problem
#include <bits/stdc++.h>
using namespace std;
#define MAX 100000
vector<int> graph[MAX + 1];
// To store the height of each node
int maxHeight, minNode;
// Function to perform dfs
void dfs(int node, int parent,
int h)
{
// Store the height of node
int height = h;
if (height > maxHeight) {
maxHeight = height;
minNode = node;
}
else if (height == maxHeight
&& minNode > node)
minNode = node;
for (int to : graph[node]) {
if (to == parent)
continue;
dfs(to, node, h + 1);
}
}
// Driver code
int main()
{
// Number of nodes
int N = 5;
// Edges of the tree
graph[1].push_back(2);
graph[1].push_back(3);
graph[2].push_back(4);
graph[2].push_back(5);
maxHeight = 0;
minNode = 1;
dfs(1, 1, 0);
cout << minNode << "\n";
return 0;
}
Java
// Java implementation of for
// the above problem
import java.util.*;
class GFG{
static final int MAX = 100000;
@SuppressWarnings("unchecked")
static Vector<Integer>[] graph = new Vector[MAX + 1];
// To store the height of each node
static int maxHeight, minNode;
// Function to perform dfs
static void dfs(int node, int parent, int h)
{
// Store the height of node
int height = h;
if (height > maxHeight)
{
maxHeight = height;
minNode = node;
}
else if (height == maxHeight &&
minNode > node)
minNode = node;
for(int to : graph[node])
{
if (to == parent)
continue;
dfs(to, node, h + 1);
}
}
// Driver code
public static void main(String[] args)
{
// Number of nodes
int N = 5;
for(int i = 0; i < graph.length; i++)
graph[i] = new Vector<Integer>();
// Edges of the tree
graph[1].add(2);
graph[1].add(3);
graph[2].add(4);
graph[2].add(5);
maxHeight = 0;
minNode = 1;
dfs(1, 1, 0);
System.out.print(minNode + "\n");
}
}
// This code is contributed by sapnasingh4991
Python3
# Python3 implementation of for # the above problem MAX = 100000 graph = [[] for i in range(MAX + 1)] # To store the height of each node maxHeight = 0 minNode = 0 # Function to perform dfs def dfs(node, parent, h): global minNode, maxHeight # Store the height of node height = h if (height > maxHeight): maxHeight = height minNode = node elif (height == maxHeight and minNode > node): minNode = node for to in graph[node]: if to == parent: continue dfs(to, node, h + 1) # Driver code if __name__=="__main__": # Number of nodes N = 5 # Edges of the tree graph[1].append(2) graph[1].append(3) graph[2].append(4) graph[2].append(5) maxHeight = 0 minNode = 1 dfs(1, 1, 0) print(minNode) # This code is contributed by rutvik_56
C#
// C# implementation of for
// the above problem
using System;
using System.Collections.Generic;
public class GFG{
static readonly int MAX = 100000;
static List<int>[] graph = new List<int>[MAX + 1];
// To store the height of each node
static int maxHeight, minNode;
// Function to perform dfs
static void dfs(int node, int parent, int h)
{
// Store the height of node
int height = h;
if (height > maxHeight)
{
maxHeight = height;
minNode = node;
}
else if (height == maxHeight &&
minNode > node)
minNode = node;
foreach(int to in graph[node])
{
if (to == parent)
continue;
dfs(to, node, h + 1);
}
}
// Driver code
public static void Main(String[] args)
{
for(int i = 0; i < graph.Length; i++)
graph[i] = new List<int>();
// Edges of the tree
graph[1].Add(2);
graph[1].Add(3);
graph[2].Add(4);
graph[2].Add(5);
maxHeight = 0;
minNode = 1;
dfs(1, 1, 0);
Console.Write(minNode + "\n");
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// Javascript implementation of for the above problem
let MAX = 100000;
let graph = new Array(MAX + 1);
// To store the height of each node
let maxHeight, minNode;
// Function to perform dfs
function dfs(node, parent, h)
{
// Store the height of node
let height = h;
if (height > maxHeight)
{
maxHeight = height;
minNode = node;
}
else if (height == maxHeight &&
minNode > node)
minNode = node;
for(let to = 0; to < graph[node].length; to++)
{
if (graph[node][to] == parent)
continue;
dfs(graph[node][to], node, h + 1);
}
}
for(let i = 0; i < graph.length; i++)
graph[i] = [];
// Edges of the tree
graph[1].push(2);
graph[1].push(3);
graph[2].push(4);
graph[2].push(5);
maxHeight = 0;
minNode = 1;
dfs(1, 1, 0);
document.write(minNode + "</br>");
// This code is contributed by decode2207.
</script>
Producción:
4
Publicación traducida automáticamente
Artículo escrito por muskan_garg y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA