Dado un árbol binario y un entero D , la tarea es verificar si la distancia entre todos los pares de los mismos valores de Node en el árbol es. D o no. Si se encuentra que es cierto, escriba Sí . De lo contrario, imprima No.
Ejemplos:
Entrada: D = 7
1 / \ 2 3 / \ / \ 4 3 4 4Salida: Sí
Explicación:
El valor repetido de los Nodes es 3 y 4.
La distancia entre los dos Nodes valorados en 3 es 3.
La distancia máxima entre cualquier par de Nodes valorados en 4 es 4.
Por lo tanto, ninguna de las distancias excede 7Entrada: D = 1
3 / \ 3 3 \ 3Salida: Sí
Planteamiento:
La idea es observar que el problema es similar a encontrar la distancia entre dos Nodes de un árbol . Pero puede haber varios pares de Nodes para los que tenemos que encontrar la distancia. Siga los pasos a continuación:
- Realice el Post Order Traversal del árbol dado y encuentre la distancia entre los pares repetidos de Nodes.
- Encuentra los Nodes que se repiten en el árbol usando unordered_map .
- Para cada Node repetido de un valor particular, encuentre la distancia máxima posible entre cualquier par.
- Si esa distancia es > D , imprima “No”.
- Si no se encuentra tal valor de Node que tenga un par que contenga ese valor, excediendo D, entonces imprima «Sí».
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Structure of a Tree node
struct Node {
int key;
struct Node *left, *right;
};
// Function to create a new node
Node* newNode(int key)
{
Node* temp = new Node;
temp->key = key;
temp->left = temp->right = NULL;
return (temp);
}
// Function to count the frequency of
// node value present in the tree
void frequencyCounts(unordered_map<int, int>& map,
Node* root)
{
if (root == NULL)
return;
map[root->key]++;
frequencyCounts(map, root->left);
frequencyCounts(map, root->right);
}
// Function that returns the max distance
// between the nodes that have the same key
int computeDistance(Node* root, int value)
{
if (root == NULL) {
return -1;
}
int left
= computeDistance(root->left, value);
int right
= computeDistance(root->right, value);
// If right and left subtree did not
// have node whose key is value
if (left == -1 && right == -1) {
// Check if the current node
// is equal to value
if (root->key == value) {
return 1;
}
else
return -1;
}
// If the left subtree has no node
// whose key is equal to value
if (left == -1) {
return right + 1;
}
// If the right subtree has no node
// whose key is equal to value
if (right == -1) {
return left + 1;
}
else {
return 1 + max(left, right);
}
return -1;
}
// Function that finds if the distance
// between any same nodes is at most K
void solve(Node* root, int dist)
{
// Create the map to look
// for same value of nodes
unordered_map<int, int> map;
// Counting the frequency of nodes
frequencyCounts(map, root);
int flag = 0;
for (auto it = map.begin();
it != map.end(); it++) {
if (it->second > 1) {
// If the returned value of
// distance is exceeds dist
int result
= computeDistance(root, it->first);
if (result > dist || result == -1) {
flag = 1;
break;
}
}
}
// Print the result
flag == 0 ? cout << "Yes\n" : cout << "No\n";
}
// Driver Code
int main()
{
Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(3);
root->right->right = newNode(4);
root->right->left = newNode(4);
int dist = 7;
solve(root, dist);
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Structure of a Tree node
static class Node
{
int key;
Node left, right;
};
// Function to create a new node
static Node newNode(int key)
{
Node temp = new Node();
temp.key = key;
temp.left = temp.right = null;
return (temp);
}
// Function to count the frequency of
// node value present in the tree
static void frequencyCounts(HashMap<Integer,
Integer> map,
Node root)
{
if (root == null)
return;
if(map.containsKey(root.key))
map.put(root.key, map.get(root.key) + 1);
else
map.put(root.key, 1);
frequencyCounts(map, root.left);
frequencyCounts(map, root.right);
}
// Function that returns the max distance
// between the nodes that have the same key
static int computeDistance(Node root, int value)
{
if (root == null)
{
return -1;
}
int left = computeDistance(root.left, value);
int right = computeDistance(root.right, value);
// If right and left subtree did not
// have node whose key is value
if (left == -1 && right == -1)
{
// Check if the current node
// is equal to value
if (root.key == value)
{
return 1;
}
else
return -1;
}
// If the left subtree has no node
// whose key is equal to value
if (left == -1)
{
return right + 1;
}
// If the right subtree has no node
// whose key is equal to value
if (right == -1)
{
return left + 1;
}
else
{
return 1 + Math.max(left, right);
}
}
// Function that finds if the distance
// between any same nodes is at most K
static void solve(Node root, int dist)
{
// Create the map to look
// for same value of nodes
HashMap<Integer,
Integer> map = new HashMap<Integer,
Integer>();
// Counting the frequency of nodes
frequencyCounts(map, root);
int flag = 0;
for(Map.Entry<Integer,
Integer> it : map.entrySet())
{
if (it.getValue() > 1)
{
// If the returned value of
// distance is exceeds dist
int result = computeDistance(
root, it.getKey());
if (result > dist || result == -1)
{
flag = 1;
break;
}
}
}
// Print the result
if(flag == 0)
System.out.print("Yes\n");
else
System.out.print("No\n");
}
// Driver Code
public static void main(String[] args)
{
Node root = newNode(1);
root.left = newNode(2);
root.right = newNode(3);
root.left.left = newNode(4);
root.left.right = newNode(3);
root.right.right = newNode(4);
root.right.left = newNode(4);
int dist = 7;
solve(root, dist);
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program to implement
# the above approach
# Structure of a Tree node
# Function to create a new node
mp = {}
class newNode:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
# Function to count the frequency
# of node value present in the tree
def frequencyCounts(root):
global mp
if (root == None):
return
mp[root.key] = mp.get(root.key, 0) + 1
frequencyCounts(root.left)
frequencyCounts(root.right)
# Function that returns the max
# distance between the nodes that
# have the same key
def computeDistance(root, value):
if (root == None):
return -1
left = computeDistance(root.left,
value)
right = computeDistance(root.right,
value)
# If right and left subtree
# did not have node whose
# key is value
if (left == -1 and
right == -1):
# Check if the current node
# is equal to value
if (root.key == value):
return 1
else:
return -1
# If the left subtree has
# no node whose key is equal
# to value
if (left == -1):
return right + 1
# If the right subtree has
# no node whose key is equal
# to value
if (right == -1):
return left + 1
else:
return 1 + max(left, right)
return -1
# Function that finds if the
# distance between any same
# nodes is at most K
def solve(root, dist):
# Create the mp to look
# for same value of nodes
global mp
# Counting the frequency
# of nodes
frequencyCounts(root)
flag = 0
for key,value in mp.items():
if(value > 1):
# If the returned value of
# distance is exceeds dist
result = computeDistance(root,
key)
if (result > dist or
result == -1):
flag = 1
break
# Print the result
if flag == 0:
print("Yes")
else:
print("No")
# Driver Code
if __name__ == '__main__':
root = newNode(1)
root.left = newNode(2)
root.right = newNode(3)
root.left.left = newNode(4)
root.left.right = newNode(3)
root.right.right = newNode(4)
root.right.left = newNode(4)
dist = 7
solve(root, dist)
# This code is contributed by SURENDRA_GANGWAR
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG{
// Structure of a Tree node
public
class Node
{
public
int key;
public
Node left, right;
};
// Function to create a new node
static Node newNode(int key)
{
Node temp = new Node();
temp.key = key;
temp.left = temp.right = null;
return (temp);
}
// Function to count the frequency of
// node value present in the tree
static void frequencyCounts(Dictionary<int, int> map,
Node root)
{
if (root == null)
return;
if(map.ContainsKey(root.key))
map[root.key] = map[root.key]+1;
else
map[root.key] = 1;
frequencyCounts(map, root.left);
frequencyCounts(map, root.right);
}
// Function that returns the max distance
// between the nodes that have the same key
static int computeDistance(Node root, int value)
{
if (root == null)
{
return -1;
}
int left = computeDistance(root.left, value);
int right = computeDistance(root.right, value);
// If right and left subtree did not
// have node whose key is value
if (left == -1 && right == -1)
{
// Check if the current node
// is equal to value
if (root.key == value)
{
return 1;
}
else
return -1;
}
// If the left subtree has no node
// whose key is equal to value
if (left == -1)
{
return right + 1;
}
// If the right subtree has no node
// whose key is equal to value
if (right == -1)
{
return left + 1;
}
else
{
return 1 + Math.Max(left, right);
}
}
// Function that finds if the distance
// between any same nodes is at most K
static void solve(Node root, int dist)
{
// Create the map to look
// for same value of nodes
Dictionary<int,
int> map = new Dictionary<int, int>();
// Counting the frequency of nodes
frequencyCounts(map, root);
int flag = 0;
foreach(KeyValuePair<int, int> it in map)
{
if (it.Value > 1)
{
// If the returned value of
// distance is exceeds dist
int result = computeDistance(
root, it.Key);
if (result > dist || result == -1)
{
flag = 1;
break;
}
}
}
// Print the result
if(flag == 0)
Console.Write("Yes\n");
else
Console.Write("No\n");
}
// Driver Code
public static void Main(String[] args)
{
Node root = newNode(1);
root.left = newNode(2);
root.right = newNode(3);
root.left.left = newNode(4);
root.left.right = newNode(3);
root.right.right = newNode(4);
root.right.left = newNode(4);
int dist = 7;
solve(root, dist);
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// Javascript Program to implement the above approach
// Structure of a Tree node
class Node
{
constructor(key) {
this.key = key;
this.left = this.right = null;
}
}
// Function to create a new node
function newNode(key)
{
let temp = new Node(key);
return (temp);
}
// Function to count the frequency of
// node value present in the tree
function frequencyCounts(map, root)
{
if (root == null)
return;
if(map.has(root.key))
map.set(root.key, map.get(root.key) + 1);
else
map.set(root.key, 1);
frequencyCounts(map, root.left);
frequencyCounts(map, root.right);
}
// Function that returns the max distance
// between the nodes that have the same key
function computeDistance(root, value)
{
if (root == null)
{
return -1;
}
let left = computeDistance(root.left, value);
let right = computeDistance(root.right, value);
// If right and left subtree did not
// have node whose key is value
if (left == -1 && right == -1)
{
// Check if the current node
// is equal to value
if (root.key == value)
{
return 1;
}
else
return -1;
}
// If the left subtree has no node
// whose key is equal to value
if (left == -1)
{
return right + 1;
}
// If the right subtree has no node
// whose key is equal to value
if (right == -1)
{
return left + 1;
}
else
{
return 1 + Math.max(left, right);
}
}
// Function that finds if the distance
// between any same nodes is at most K
function solve(root, dist)
{
// Create the map to look
// for same value of nodes
let map = new Map();
// Counting the frequency of nodes
frequencyCounts(map, root);
let flag = 0;
map.forEach((values,keys)=>{
if (values > 1)
{
// If the returned value of
// distance is exceeds dist
let result = computeDistance(root, keys);
if (result > dist || result == -1)
{
flag = 1;
map.clear();
}
}
})
// Print the result
if(flag == 0)
document.write("Yes");
else
document.write("No");
}
let root = newNode(1);
root.left = newNode(2);
root.right = newNode(3);
root.left.left = newNode(4);
root.left.right = newNode(3);
root.right.right = newNode(4);
root.right.left = newNode(4);
let dist = 7;
solve(root, dist);
</script>
Producción:
Yes
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)