Dado un árbol binario que consta de N Nodes enraizados en 1 , un número entero K y una array arr[] que consta de valores asignados a cada Node, la tarea es contar el número de rutas de raíz a hoja que tienen exactamente K Nodes distintos en el binario dado. Árbol.
Ejemplos:
Entrada: N = 3, Edges[][] = {{1, 2}, {1, 3}}, arr[] = {3, 3, 2}, K = 2, A continuación se muestra el árbol dado:
Salida: 1
Explicación:
existe solo 1 ruta distinta, es decir, la ruta 1 -> 3 contiene 2 Nodes distintos.
Por lo tanto, la respuesta es 1.Entrada: N = 7, Bordes[][] = {{1, 2}, {1, 3}, {2, 4}, {2, 5}, {3, 6}, {3, 7}}, arr[] = {2, 2, 2, 2, 3, 5, 2}, K = 1, a continuación se muestra el árbol dado:
Salida: 2
Explicación:
Solo existen 2 rutas distintas que contienen 1 Node distinto:
1) Rutas 1 -> 2 -> 4,
2) Rutas 1 -> 3 -> 7
Por lo tanto, la respuesta es 2.
Enfoque ingenuo: el enfoque más simple es generar todas las rutas posibles desde la raíz hasta los Nodes hoja y, para cada ruta, verificar si contiene K Nodes distintos o no. Finalmente, imprima el recuento de dichos caminos.
Complejidad temporal: O(N * H 2 ), donde H denota la altura del árbol.
Espacio Auxiliar: O(N);
Enfoque eficiente: la idea es usar Preorder Traversal y un mapa para contar el Node distinto en la ruta desde la raíz hasta el Node actual. Siga los pasos a continuación para resolver el problema:
- Inicialice una variable different_nodes como 0 para almacenar el recuento del Node distinto desde la raíz hasta el Node actual y ans como 0 para almacenar el total de rutas distintas de la raíz a la hoja que tienen K Nodes distintos.
- Realice Preorder Traversal en el árbol binario dado y almacene el recuento del Node distinto desde la raíz hasta el Node actual en el mapa M .
- Cada vez que aparece un Node por primera vez en una ruta, aumente el recuento de Nodes distintos en 1 .
- Si el recuento de Nodes distintos en una ruta es mayor que K , regrese al Node principal del Node actual.
- De lo contrario, continúe visitando los hijos del Node actual incrementando la frecuencia del valor del Node actual en 1 .
- En el paso anterior, incremente ans en 1 si el recuento de Nodes distintos en esa ruta de raíz a hoja es exactamente igual a K .
- Después de los pasos anteriores, imprima el valor de ans como el conteo resultante.
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;
// Structure of a Tree Node
struct Node {
int key;
Node *left, *right;
};
// Function to create new tree node
Node* newNode(int key)
{
Node* temp = new Node;
temp->key = key;
temp->left = temp->right = NULL;
return temp;
}
// Function to count all root to leaf
// paths having K distinct nodes
void findkDistinctNodePaths(
Node* root, unordered_map<int, int> freq,
int distinct_nodes, int k, int& ans)
{
// If current node is null
if (root == NULL)
return;
// Update count of distinct nodes
if (freq[root->key] == 0)
distinct_nodes++;
// If count > k then return to
// the parent node
if (distinct_nodes > k)
return;
// Update frequency of current node
freq[root->key]++;
// Go to the left subtree
findkDistinctNodePaths(root->left,
freq,
distinct_nodes,
k, ans);
// Go to the right subtree
findkDistinctNodePaths(root->right,
freq,
distinct_nodes,
k, ans);
// If current node is leaf node
if (root->left == NULL
&& root->right == NULL) {
// If count of distinct node
// is same as K, increment ans
if (distinct_nodes == k)
ans++;
}
}
// Function to find count of root to
// leaf paths having K distinct node
void printkDistinctNodePaths(Node* root,
int k)
{
// Initialize unordered map
unordered_map<int, int> freq;
// Stores count of distinct node
int distinct_nodes = 0;
// Stores total count of nodes
int ans = 0;
// Perform Preorder Traversal
findkDistinctNodePaths(root, freq,
distinct_nodes,
k, ans);
// Print the final count
cout << ans;
}
// Driver Code
int main()
{
/* 2
/ \
/ \
1 3
/ \ / \
/ \ / \
4 2 -5 3
*/
// Given Binary Tree
Node* root = newNode(2);
root->left = newNode(1);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(2);
root->right->left = newNode(-5);
root->right->right = newNode(3);
// Given K
int K = 2;
// Function Call
printkDistinctNodePaths(root, K);
return 0;
}
Java
// Java program for the
// above approach
import java.util.*;
class GFG{
// Structure of a
// Tree Node
static class Node
{
int key;
Node left, right;
};
static int ans;
// Function to create
// new tree node
static Node newNode(int key)
{
Node temp = new Node();
temp.key = key;
temp.left = temp.right = null;
return temp;
}
// Function to count all root
// to leaf paths having K
// distinct nodes
static void findkDistinctNodePaths(Node root,
HashMap<Integer,
Integer> freq,
int distinct_nodes,
int k)
{
// If current node is null
if (root == null)
return;
// Update count of distinct nodes
if (!freq.containsKey(root.key))
distinct_nodes++;
// If count > k then return
// to the parent node
if (distinct_nodes > k)
return;
// Update frequency of
// current node
if(freq.containsKey(root.key))
{
freq.put(root.key,
freq.get(root.key) + 1);
}
else
{
freq.put(root.key, 1);
}
// Go to the left subtree
findkDistinctNodePaths(root.left, freq,
distinct_nodes, k);
// Go to the right subtree
findkDistinctNodePaths(root.right, freq,
distinct_nodes, k);
// If current node is
// leaf node
if (root.left == null &&
root.right == null)
{
// If count of distinct node
// is same as K, increment ans
if (distinct_nodes == k)
ans++;
}
}
// Function to find count of root to
// leaf paths having K distinct node
static void printkDistinctNodePaths(Node root,
int k)
{
// Initialize unordered map
HashMap<Integer,
Integer> freq = new HashMap<>();
// Stores count of
// distinct node
int distinct_nodes = 0;
// Stores total
// count of nodes
ans = 0;
// Perform Preorder Traversal
findkDistinctNodePaths(root, freq,
distinct_nodes, k);
// Print the final count
System.out.print(ans);
}
// Driver Code
public static void main(String[] args)
{
/* 2
/ \
/ \
1 3
/ \ / \
/ \ / \
4 2 -5 3
*/
// Given Binary Tree
Node root = newNode(2);
root.left = newNode(1);
root.right = newNode(3);
root.left.left = newNode(4);
root.left.right = newNode(2);
root.right.left = newNode(-5);
root.right.right = newNode(3);
// Given K
int K = 2;
// Function Call
printkDistinctNodePaths(root, K);
}
}
// This code is contributed by gauravrajput1
Python3
# Python3 program for the above approach
# Structure of a Tree Node
class newNode:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
ans = 0
# Function to count all root to leaf
# paths having K distinct nodes
def findkDistinctNodePaths(root, freq,
distinct_nodes, k):
global ans
# If current node is None
if (root == None):
return
# Update count of distinct nodes
if (root.key not in freq):
distinct_nodes += 1
# If count > k then return to
# the parent node
if (distinct_nodes > k):
return
# Update frequency of current node
if (root.key in freq):
freq[root.key] += 1
else:
freq[root.key] = freq.get(root.key, 0) + 1
# Go to the left subtree
findkDistinctNodePaths(root.left, freq,
distinct_nodes, k)
# Go to the right subtree
findkDistinctNodePaths(root.right, freq,
distinct_nodes, k)
# If current node is leaf node
if (root.left == None and
root.right == None):
# If count of distinct node
# is same as K, increment ans
if (distinct_nodes == k):
ans += 1
# Function to find count of root to
# leaf paths having K distinct node
def printkDistinctNodePaths(root, k):
global ans
# Initialize unordered map
freq = {}
# Stores count of distinct node
distinct_nodes = 0
# Perform Preorder Traversal
findkDistinctNodePaths(root, freq,
distinct_nodes, k)
# Print the final count
print(ans)
# Driver Code
if __name__ == '__main__':
''' 2
/ \
/ \
1 3
/ \ / \
/ \ / \
4 2 -5 3
'''
# Given Binary Tree
root = newNode(2)
root.left = newNode(1)
root.right = newNode(3)
root.left.left = newNode(4)
root.left.right = newNode(2)
root.right.left = newNode(-5)
root.right.right = newNode(3)
# Given K
K = 2
# Function Call
printkDistinctNodePaths(root, K)
# This code is contributed by SURENDRA_GANGWAR
C#
// C# program for 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;
};
static int ans;
// Function to create
// new tree node
static Node newNode(int key)
{
Node temp = new Node();
temp.key = key;
temp.left = temp.right = null;
return temp;
}
// Function to count all root
// to leaf paths having K
// distinct nodes
static void findkDistinctNodePaths(Node root,
Dictionary<int, int> freq,
int distinct_nodes,
int k)
{
// If current node is null
if (root == null)
return;
// Update count of distinct nodes
if (!freq.ContainsKey(root.key))
distinct_nodes++;
// If count > k then return
// to the parent node
if (distinct_nodes > k)
return;
// Update frequency of
// current node
if (freq.ContainsKey(root.key))
{
freq[root.key] = freq[root.key] + 1;
}
else
{
freq.Add(root.key, 1);
}
// Go to the left subtree
findkDistinctNodePaths(root.left, freq,
distinct_nodes, k);
// Go to the right subtree
findkDistinctNodePaths(root.right, freq,
distinct_nodes, k);
// If current node is
// leaf node
if (root.left == null &&
root.right == null)
{
// If count of distinct node
// is same as K, increment ans
if (distinct_nodes == k)
ans++;
}
}
// Function to find count of root to
// leaf paths having K distinct node
static void printkDistinctNodePaths(Node root,
int k)
{
// Initialize unordered map
Dictionary<int,
int> freq = new Dictionary<int,
int>();
// Stores count of
// distinct node
int distinct_nodes = 0;
// Stores total
// count of nodes
ans = 0;
// Perform Preorder Traversal
findkDistinctNodePaths(root, freq,
distinct_nodes, k);
// Print the readonly count
Console.Write(ans);
}
// Driver Code
public static void Main(String[] args)
{
/* 2
/ \
/ \
1 3
/ \ / \
/ \ / \
4 2 -5 3
*/
// Given Binary Tree
Node root = newNode(2);
root.left = newNode(1);
root.right = newNode(3);
root.left.left = newNode(4);
root.left.right = newNode(2);
root.right.left = newNode(-5);
root.right.right = newNode(3);
// Given K
int K = 2;
// Function Call
printkDistinctNodePaths(root, K);
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// Javascript program for the above approach
// Structure of tree node
class Node
{
constructor(key)
{
this.left = null;
this.right = null;
this.key = key;
}
}
let ans;
// Function to create
// new tree node
function newNode(key)
{
let temp = new Node(key);
return temp;
}
// Function to count all root
// to leaf paths having K
// distinct nodes
function findkDistinctNodePaths(root, freq,
distinct_nodes, k)
{
// If current node is null
if (root == null)
return;
// Update count of distinct nodes
if (!freq.has(root.key))
distinct_nodes++;
// If count > k then return
// to the parent node
if (distinct_nodes > k)
return;
// Update frequency of
// current node
if (freq.has(root.key))
{
freq.set(root.key,
freq.get(root.key) + 1);
}
else
{
freq.set(root.key, 1);
}
// Go to the left subtree
findkDistinctNodePaths(root.left, freq,
distinct_nodes, k);
// Go to the right subtree
findkDistinctNodePaths(root.right, freq,
distinct_nodes, k);
// If current node is
// leaf node
if (root.left == null &&
root.right == null)
{
// If count of distinct node
// is same as K, increment ans
if (distinct_nodes == k)
ans++;
}
}
// Function to find count of root to
// leaf paths having K distinct node
function printkDistinctNodePaths(root, k)
{
// Initialize unordered map
let freq = new Map();
// Stores count of
// distinct node
let distinct_nodes = 0;
// Stores total
// count of nodes
ans = 0;
// Perform Preorder Traversal
findkDistinctNodePaths(root, freq,
distinct_nodes, k);
// Print the final count
document.write(ans);
}
// Driver code
/* 2
/ \
/ \
1 3
/ \ / \
/ \ / \
4 2 -5 3
*/
// Given Binary Tree
let root = newNode(2);
root.left = newNode(1);
root.right = newNode(3);
root.left.left = newNode(4);
root.left.right = newNode(2);
root.right.left = newNode(-5);
root.right.right = newNode(3);
// Given K
let K = 2;
// Function Call
printkDistinctNodePaths(root, K);
// This code is contributed by suresh07
</script>
Producción:
2
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por kundudinesh007 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA