Dado un N ario Tree que consta de N Nodes, la tarea es encontrar la distancia mínima del Node A al Node B del árbol.
Ejemplos :
Entrada :
1
/ \
2 3
/ \ / \ \
4 5 6 7 8
A = 4, B = 3
Salida : 3
Explicación : El camino 4->2->1->3 da la distancia mínima de A a B.Entrada :
1
/ \
2 3
/ \ \
6 7 8
A = 6, B = 7
Salida : 2
Enfoque: este problema se puede resolver utilizando el concepto de LCA (Ancestro común más bajo) . La distancia mínima entre dos Nodes dados A y B se puede encontrar usando la fórmula:
distancia mental (A, B) = dist (LCA, A) + dist (LCA, B)
Siga los pasos a continuación para resolver el problema:
- Encuentre la ruta desde el Node raíz a los Nodes A y B , respectivamente, y almacene simultáneamente las dos rutas en dos arrays.
- Ahora itere hasta que los valores de ambas arrays sean iguales y el valor justo antes de la discrepancia sea el valor del Node LCA .
- El valor justo antes de la discrepancia es el valor del Node LCA .
- Encuentre la distancia desde el Node LCA al Node A y B , que se puede encontrar con los pasos dados:
- En la primera array, itere desde el valor del Node LCA y aumente el conteo hasta que se encuentre el valor del Node A , que es dist (LCA, A).
- En la segunda array, itere desde el valor del Node LCA y aumente el conteo hasta que se encuentre el valor del Node B, que es dist (LCA, B)
- Devuelve la suma de esas distancias, es decir , dist (LCA, A) + dist (LCA, B) .
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Structure of Node
struct Node {
int val;
vector<Node*> child;
};
// Utility function to create a
// new tree node
Node* newNode(int key)
{
Node* temp = new Node;
temp->val = key;
return temp;
}
bool flag;
// Function to get the path
// from root to a node
void findPath(Node* root, int key,
vector<int>& arr)
{
if (!root)
return;
arr.push_back(root->val);
// if key is found set flag and return
if (root->val == key) {
flag = 1;
return;
}
// recur for all children
for (int i = 0; i < root->child.size(); i++) {
findPath(root->child[i], key, arr);
// if key is found dont need to pop values
if (flag == 1)
return;
}
arr.pop_back();
return;
}
void findMinDist(Node* root, int A, int B)
{
if (root == NULL)
return;
int val = root->val;
// vector to store both paths
vector<int> arr1, arr2;
// set flag as false;
flag = false;
// find path from root to node a
findPath(root, A, arr1);
// set flag again as false;
flag = false;
// find path from root to node b
findPath(root, B, arr2);
// to store index of LCA node
int j;
// if unequal values are found
// return previous value
for (int i = 1; i < min(arr1.size(), arr2.size()); i++) {
if (arr1[i] != arr2[i]) {
val = arr1[i - 1];
j = i - 1;
break;
}
}
int d1 = 0, d2 = 0;
// iterate for finding distance
// between LCA(a, b) and a
for (int i = j; i < arr1.size(); i++)
if (arr1[i] == A)
break;
else
d1 += 1;
// iterate for finding distance
// between LCA(a, b) and b
for (int i = j; i < arr2.size(); i++)
if (arr2[i] == B)
break;
else
d2 += 1;
// get distance
val = d1 + d2;
cout << val << '\n';
}
// Driver Code
int main()
{
Node* root = newNode(1);
(root->child).push_back(newNode(2));
(root->child).push_back(newNode(3));
(root->child[0]->child).push_back(newNode(4));
(root->child[0]->child).push_back(newNode(5));
(root->child[1]->child).push_back(newNode(6));
(root->child[1])->child.push_back(newNode(7));
(root->child[1]->child).push_back(newNode(8));
int A = 4, B = 3;
// get min distance
findMinDist(root, A, B);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
public class Main
{
// Structure of Node
static class Node {
public int val;
public Node left, right;
public Vector<Node> child;
public Node(int key)
{
val = key;
left = right = null;
child = new Vector<Node>();
}
}
// Utility function to create a
// new tree node
static Node newNode(int key)
{
Node temp = new Node(key);
return temp;
}
static int flag;
// Function to get the path
// from root to a node
static void findPath(Node root, int key,
Vector<Integer> arr)
{
if (root==null)
return;
arr.add(root.val);
// if key is found set flag and return
if (root.val == key) {
flag = 1;
return;
}
// recur for all children
for (int i = 0; i < root.child.size(); i++) {
findPath(root.child.get(i), key, arr);
// if key is found dont need to pop values
if (flag == 1)
return;
}
arr.remove(arr.size()-1);
return;
}
static void findMinDist(Node root, int A, int B)
{
if (root == null)
return;
int val = root.val;
// vector to store both paths
Vector<Integer> arr1 = new Vector<Integer>();
Vector<Integer> arr2 = new Vector<Integer>();
// set flag as false;
flag = 0;
// find path from root to node a
findPath(root, A, arr1);
// set flag again as false;
flag = 0;
// find path from root to node b
findPath(root, B, arr2);
// to store index of LCA node
int j=0;
// if unequal values are found
// return previous value
for (int i = 1; i < Math.min(arr1.size(), arr2.size()); i++) {
if (arr1.get(i) != arr2.get(i)) {
val = arr1.get(i - 1);
j = i - 1;
break;
}
}
int d1 = 0, d2 = 0;
// iterate for finding distance
// between LCA(a, b) and a
for (int i = j; i < arr1.size(); i++)
if (arr1.get(i) == A)
break;
else
d1 += 1;
// iterate for finding distance
// between LCA(a, b) and b
for (int i = j; i < arr2.size(); i++)
if (arr2.get(i) == B)
break;
else
d2 += 1;
// get distance
val = d1 + d2;
System.out.println(val);
}
public static void main(String[] args) {
Node root = newNode(1);
(root.child).add(newNode(2));
(root.child).add(newNode(3));
(root.child.get(0).child).add(newNode(4));
(root.child.get(0).child).add(newNode(5));
(root.child.get(1).child).add(newNode(6));
(root.child.get(1)).child.add(newNode(7));
(root.child.get(1).child).add(newNode(8));
int A = 4, B = 3;
// get min distance
findMinDist(root, A, B);
}
}
// This code is contributed by mukesh07.
Python3
# Python3 program for the above approach # Structure of Node class Node: def __init__(self, key): self.val = key self.left = None self.right = None self.child = [] # Utility function to create a # new tree node def newNode(key): temp = Node(key) return temp flag = 0 # Function to get the path # from root to a node def findPath(root, key, arr): global flag if (root==None): return arr.append(root.val) # if key is found set flag and return if (root.val == key): flag = 1 return # recur for all children for i in range(len(root.child)): findPath(root.child[i], key, arr) # if key is found dont need to pop values if (flag == 1): return arr.pop() return def findMinDist(root, A, B): global flag if (root == None): return val = root.val # vector to store both paths arr1 = [] arr2 = [] # set flag as false; flag = 0 # find path from root to node a findPath(root, A, arr1) # set flag again as false; flag = 0 # find path from root to node b findPath(root, B, arr2) # to store index of LCA node j=0 # if unequal values are found # return previous value for i in range(min(len(arr1), len(arr2))): if (arr1[i] != arr2[i]): val = arr1[i - 1] j = i - 1 break d1, d2 = 0, 0 # iterate for finding distance # between LCA(a, b) and a for i in range(j, len(arr1)): if (arr1[i] == A): break else: d1 += 1 # iterate for finding distance # between LCA(a, b) and b for i in range(j, len(arr2)): if (arr2[i] == B): break else: d2 += 1 # get distance val = d1 + d2 print(val) root = newNode(1) (root.child).append(newNode(2)) (root.child).append(newNode(3)) (root.child[0].child).append(newNode(4)) (root.child[0].child).append(newNode(5)) (root.child[1].child).append(newNode(6)) (root.child[1]).child.append(newNode(7)) (root.child[1].child).append(newNode(8)) A, B = 4, 3 # get min distance findMinDist(root, A, B) # This code is contributed by rameshtravel07.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
// Structure of Node
class GFG{
public class Node {
public int val;
public Node left=null, right=null;
public List<Node> child = new List<Node>();
}
// Utility function to create a
// new tree node
static Node newNode(int key)
{
Node temp = new Node();
temp.val = key;
return temp;
}
static int flag;
// Function to get the path
// from root to a node
static void findPath(Node root, int key,
List<int> arr)
{
if (root==null)
return;
arr.Add(root.val);
// if key is found set flag and return
if (root.val == key) {
flag = 1;
return;
}
// recur for all children
for (int i = 0; i < root.child.Count; i++) {
findPath(root.child[i], key, arr);
// if key is found dont need to pop values
if (flag == 1)
return;
}
arr.RemoveAt(arr.Count-1);
return;
}
static void findMinDist(Node root, int A, int B)
{
if (root == null)
return;
int val = root.val;
// vector to store both paths
List<int> arr1 = new List<int>();
List<int> arr2 = new List<int>();
// set flag as false;
flag = 0;
// find path from root to node a
findPath(root, A, arr1);
// set flag again as false;
flag = 0;
// find path from root to node b
findPath(root, B, arr2);
// to store index of LCA node
int j=0;
// if unequal values are found
// return previous value
for (int i = 1; i < Math.Min(arr1.Count, arr2.Count); i++) {
if (arr1[i] != arr2[i]) {
val = arr1[i - 1];
j = i - 1;
break;
}
}
int d1 = 0, d2 = 0;
// iterate for finding distance
// between LCA(a, b) and a
for (int i = j; i < arr1.Count; i++)
if (arr1[i] == A)
break;
else
d1 += 1;
// iterate for finding distance
// between LCA(a, b) and b
for (int i = j; i < arr2.Count; i++)
if (arr2[i] == B)
break;
else
d2 += 1;
// get distance
val = d1 + d2;
Console.WriteLine(val);
}
// Driver Code
public static void Main()
{
Node root = newNode(1);
(root.child).Add(newNode(2));
(root.child).Add(newNode(3));
(root.child[0].child).Add(newNode(4));
(root.child[0].child).Add(newNode(5));
(root.child[1].child).Add(newNode(6));
(root.child[1]).child.Add(newNode(7));
(root.child[1].child).Add(newNode(8));
int A = 4, B = 3;
// get min distance
findMinDist(root, A, B);
}
}
// This code is contributed by SURENDRA_GANGWAR.
Javascript
<script>
// Javascript program for the above approach
// Structure of Node
class Node
{
constructor(key) {
this.left = null;
this.right = null;
this.val = key;
this.child = [];
}
}
// Utility function to create a
// new tree node
function newNode(key)
{
let temp = new Node(key);
return temp;
}
let flag;
// Function to get the path
// from root to a node
function findPath(root, key, arr)
{
if (root==null)
return;
arr.push(root.val);
// if key is found set flag and return
if (root.val == key) {
flag = 1;
return;
}
// recur for all children
for (let i = 0; i < root.child.length; i++) {
findPath(root.child[i], key, arr);
// if key is found dont need to pop values
if (flag == 1)
return;
}
arr.pop();
return;
}
function findMinDist(root, A, B)
{
if (root == null)
return;
let val = root.val;
// vector to store both paths
let arr1 = [];
let arr2 = [];
// set flag as false;
flag = 0;
// find path from root to node a
findPath(root, A, arr1);
// set flag again as false;
flag = 0;
// find path from root to node b
findPath(root, B, arr2);
// to store index of LCA node
let j=0;
// if unequal values are found
// return previous value
for (let i = 1; i < Math.min(arr1.length, arr2.length); i++) {
if (arr1[i] != arr2[i]) {
val = arr1[i - 1];
j = i - 1;
break;
}
}
let d1 = 0, d2 = 0;
// iterate for finding distance
// between LCA(a, b) and a
for (let i = j; i < arr1.length; i++)
if (arr1[i] == A)
break;
else
d1 += 1;
// iterate for finding distance
// between LCA(a, b) and b
for (let i = j; i < arr2.length; i++)
if (arr2[i] == B)
break;
else
d2 += 1;
// get distance
val = d1 + d2;
document.write(val);
}
let root = newNode(1);
(root.child).push(newNode(2));
(root.child).push(newNode(3));
(root.child[0].child).push(newNode(4));
(root.child[0].child).push(newNode(5));
(root.child[1].child).push(newNode(6));
(root.child[1]).child.push(newNode(7));
(root.child[1].child).push(newNode(8));
let A = 4, B = 3;
// get min distance
findMinDist(root, A, B);
// This code is contributed by decode2207.
</script>
Producción
3
Complejidad temporal: O(N).
Espacio Auxiliar: O(N).
Publicación traducida automáticamente
Artículo escrito por sohailahmed46khan786 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA