el coronavirus, es
Ejemplos:
Aporte:
1
/ \
2 3
\
4
\
5
\
6
Producto: 2
Explicación:
Los kits de vacunas se deben suministrar a las casas números 1 y 5.Aporte:
1
/ \
2 3
Producto: 1
Explicación:
Los kits de vacunas se deben suministrar a la casa número 1.
Enfoque: Este problema se puede resolver mediante programación dinámica .
- Cree una tabla hash para controlar todos los Nodes visitados.
- La función recursiva debe devolver el número de Nodes secundarios por debajo de los cuales no se han visitado.
- Si el Node es NULL, devuelve 0. Esta será nuestra condición base.
- Cree una variable de contador para almacenar el número de Nodes secundarios no visitados e inicialícelo mediante la llamada recursiva para los Nodes secundarios izquierdo y derecho.
- Si la variable de contador es cero, se han visitado todos los Nodes secundarios. Si el Node actual no está visitado y no es el Node raíz, devolvemos 1 ya que hay un Node, es decir, el Node actual que no está visitado.
- Si el Node actual no está visitado y la variable contador también es cero y si el Node actual es el Node raíz, incrementamos la respuesta en 1 y devolvemos 1.
- De lo contrario, si la variable de contador es mayor que cero, marcamos el Node principal, el Node actual y los Nodes secundarios como visitados e incrementamos la respuesta en 1.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
// Structure of a tree node
struct Node {
int data;
Node* left;
Node* right;
Node(int val)
{
data = val;
left = right = NULL;
}
};
// Function to implement the dp
int solve(int& ans, Node* root, Node* parent,
unordered_map<Node*, int>& dp)
{
// Base Condition
if (root == 0)
return 0;
// Counter Variable to store the number
// of unvisited child elements for
// the current node
int cnt = solve(ans, root->left, root, dp);
cnt += solve(ans, root->right, root, dp);
// If there are no unvisited child nodes
if (cnt == 0) {
// If the current node is root
// node and unvisited increment
// the answer by 1
if (dp[root] == 0 && parent == 0) {
ans++;
return 1;
}
// If the current node is unvisited
// but it is not the root node
if (dp[root] == 0)
return 1;
// If the current node is also visited
return 0;
}
// If there are unvisited child nodes
else {
// Mark the current node,
// parent node and child
// nodes as visited
if (root->left != 0)
dp[root->left] = 1;
if (root->right != 0)
dp[root->right] = 1;
dp[root] = 1;
if (parent != 0)
dp[parent] = 1;
// Increment the answer by 1
ans++;
// Return 0 as now we have marked
// all nodes as visited
return 0;
}
}
// Function to find required vaccines
int supplyVaccine(Node* root)
{
unordered_map<Node*, int> dp;
int ans = 0;
// Passing parent of root
// node as NULL to identify it
solve(ans, root, 0, dp);
return ans;
}
// Driver Code
int main()
{
string treeString;
Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->right->right = new Node(4);
root->right->right->right = new Node(5);
root->right->right->right->right
= new Node(6);
// Function call
cout << supplyVaccine(root) << "\n";
return 0;
}
Java
// Java code to implement the approach
import java.util.*;
class GFG {
// Structure of a tree node
static class Node {
int data;
Node left;
Node right;
Node(int val) {
data = val;
left = right = null;
}
};
static int ans;
static HashMap<Node, Integer> dp;
// Function to implement the dp
static int solve(Node root, Node parent)
{
// Base Condition
if (root == null)
return 0;
// Counter Variable to store the number
// of unvisited child elements for
// the current node
ans = solve(root.left, root);
ans += solve(root.right, root);
// If there are no unvisited child nodes
if (ans == 0) {
// If the current node is root
// node and unvisited increment
// the answer by 1
if (dp.get(root) == null && parent == null) {
ans++;
return 1;
}
// If the current node is unvisited
// but it is not the root node
if (dp.get(root) == null)
return 1;
// If the current node is also visited
}
// If there are unvisited child nodes
else
{
// Mark the current node,
// parent node and child
// nodes as visited
if (root.left != null)
dp.put(root.left, 1);
if (root.right != null)
dp.put(root.right, 1);
dp.put(root, 1);
if (parent != null)
dp.put(parent, 1);
// Return 0 as now we have marked
// all nodes as visited
}
return 0;
}
// Function to find required vaccines
static void supplyVaccine(Node root) {
dp = new HashMap<>();
ans = 0;
// Passing parent of root
// node as null to identify it
solve(root, root);
}
// Driver Code
public static void main(String[] args) {
String treeString;
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.right.right = new Node(4);
root.right.right.right = new Node(5);
root.right.right.right.right = new Node(6);
// Function call
supplyVaccine(root);
System.out.print(ans + "\n");
}
}
// This code is contributed by shikhasingrajput
Python3
# Python code to implement the approach
# Structure of a tree node
class Node:
def __init__(self, val):
self.data = val
self.left = None
self.right = None
dp = {}
ans = 0
# Function to implement the dp
def solve(root, parent):
global dp
global ans
# Base Condition
if (root == None):
return 0
# Counter Variable to store the number
# of unvisited child elements for
# the current node
ans = solve(root.left, root)
ans += solve(root.right, root)
# If there are no unvisited child nodes
if (ans == 0):
# If the current node is root
# node and unvisited increment
# the answer by 1
if (root not in dp and parent == None):
ans += 1
return 1
# If the current node is unvisited
# but it is not the root node
if (root not in dp):
return 1
# If the current node is also visited
# If there are unvisited child nodes
else:
# Mark the current node,
# parent node and child
# nodes as visited
if (root.left != None):
dp[root.left] = 1
if (root.right != None):
dp[root.right] = 1
dp[root] = 1
if (parent != None):
dp[parent] = 1
# Return 0 as now we have marked
# all nodes as visited
return 0
# Function to find required vaccines
def supplyVaccine(root):
global ans
# Passing parent of root
# node as None to identify it
solve(root, root)
# Driver Code
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.right.right = Node(4)
root.right.right.right = Node(5)
root.right.right.right.right = Node(6)
# Function call
supplyVaccine(root)
print(ans)
# This code is contributed by shinjanpatra
C#
//C# program to implement the approach
using System;
using System.Collections.Generic;
public class GFG{
// Structure of a tree node
class Node {
public int data;
public Node left;
public Node right;
public Node(int val){
this.data=val;
this.left=this.right=null;
}
}
static int ans;
static Dictionary<Node, int> dp;
// Function to implement the dp
static int solve(Node root, Node parent)
{
// Base Condition
if (root == null)
return 0;
// Counter Variable to store the number
// of unvisited child elements for
// the current node
ans = solve(root.left, root);
ans += solve(root.right, root);
// If there are no unvisited child nodes
if (ans == 0) {
// If the current node is root
// node and unvisited increment
// the answer by 1
if (!dp.ContainsKey(root) && parent == null) {
ans++;
return 1;
}
// If the current node is unvisited
// but it is not the root node
if (!dp.ContainsKey(root))
return 1;
// If the current node is also visited
}
// If there are unvisited child nodes
else
{
// Mark the current node,
// parent node and child
// nodes as visited
if (root.left != null)
dp[root.left]=1;
if (root.right != null)
dp[root.right]=1;
dp[root]=1;
if (parent != null)
dp[parent]=1;
// Return 0 as now we have marked
// all nodes as visited
}
return 0;
}
// Function to find required vaccines
static void supplyVaccine(Node root) {
dp = new Dictionary<Node,int>();
ans = 0;
// Passing parent of root
// node as null to identify it
solve(root, root);
}
//Driver Code
static public void Main (){
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.right.right = new Node(4);
root.right.right.right = new Node(5);
root.right.right.right.right = new Node(6);
// Function call
supplyVaccine(root);
Console.Write(ans);
}
}
// This code is contributed by shruti456rawal
Javascript
<script>
// javascript code to implement the approach
// Structure of a tree node
class Node
{
constructor(val) {
this.data = val;
this.left = this.right = null;
}
}
var ans;
var dp = new Map();
// Function to implement the dp
function solve(root, parent) {
// Base Condition
if (root == null)
return 0;
// Counter Variable to store the number
// of unvisited child elements for
// the current node
ans = solve(root.left, root);
ans += solve(root.right, root);
// If there are no unvisited child nodes
if (ans == 0) {
// If the current node is root
// node and unvisited increment
// the answer by 1
if (dp.get(root) == null && parent == null) {
ans++;
return 1;
}
// If the current node is unvisited
// but it is not the root node
if (dp.get(root) == null)
return 1;
// If the current node is also visited
}
// If there are unvisited child nodes
else {
// Mark the current node,
// parent node and child
// nodes as visited
if (root.left != null)
dp.set(root.left, 1);
if (root.right != null)
dp.set(root.right, 1);
dp.set(root, 1);
if (parent != null)
dp.set(parent, 1);
// Return 0 as now we have marked
// all nodes as visited
}
return 0;
}
// Function to find required vaccines
function supplyVaccine(root) {
ans = 0;
// Passing parent of root
// node as null to identify it
solve(root, root);
}
// Driver Code
var root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.right.right = new Node(4);
root.right.right.right = new Node(5);
root.right.right.right.right = new Node(6);
// Function call
supplyVaccine(root);
document.write(ans + "\n");
// This code contributed by shikhasingrajput
</script>
Producción
2
Complejidad temporal: O(N).
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por ishankhandelwals y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA