Número mínimo de cámaras requeridas para monitorear todos los Nodes de un árbol binario

Posted on by Rudeus Greyrat

Dado un árbol binario que consta de N Nodes, la tarea es encontrar la cantidad mínima de cámaras requeridas para monitorear todo el árbol de manera que cada cámara ubicada en cualquier Node pueda monitorear el Node mismo, su padre y sus hijos inmediatos.

Ejemplos:

Entrada:
             0
           /
        0
      /\
    0 0
Salida: 1
Explicación:
             0
           /
        0  <———- Cámara
      / \
   0 0
En el árbol anterior, los Nodes que están en negrita son los Nodes que tienen la cámara. Colocando la cámara en el nivel 1 del Árbol se pueden monitorear todos los Nodes del Árbol Binario dado.
Por lo tanto, el número mínimo de cámaras necesario es 1.

Entrada:
             0
           /
        0
      /
    0 
      \
       0
Salida: 2

Enfoque: el problema dado se puede resolver almacenando los estados de los Nodes, ya sea que la cámara se haya colocado o no, o que el Node sea monitoreado por cualquier otro Node que tenga la cámara o no. La idea es realizar el DFS Traversal en el árbol dado y devolver los estados de cada Node en cada llamada recursiva . Considere la siguiente conversión como los estados devueltos por la función:

  • Si el valor es 1 , el Node es monitoreado.
  • Si el valor es 2 , el Node no se supervisa.
  • Si el valor es 3 , el Node tiene la cámara.

Siga los pasos a continuación para resolver el problema:

  • Inicialice una variable, digamos count para almacenar el número mínimo de cámaras requeridas para monitorear todos los Nodes del árbol dado.
  • Cree una función , digamos dfs (raíz) que tome la raíz del árbol dado y devuelva el estado de cada Node, ya sea que se haya colocado la cámara o no, o si el Node es monitoreado por cualquier otro Node que tenga la cámara y realice los siguientes pasos :
    • Si el valor del Node es NULL , devuelva 1 ya que el Node NULL siempre se supervisa.
    • Llame recursivamente al subárbol izquierdo y derecho y almacene el valor devuelto por ellos en las variables L y R .
    • Si el valor de L y R es 1 , devuelva 2 de la llamada recursiva actual, ya que el Node raíz actual no se supervisa.
    • Si el valor de L o R es 2 , incremente el valor de count en 1 como uno de los Nodes izquierdo y derecho no se monitorea y devuelva 3 .
    • De lo contrario, devuelve 1 .
  • Llame a la función recursiva anterior desde la raíz y si el valor que devuelve es 2 , incremente el valor de count en 1 .
  • Después de completar los pasos anteriores, imprima el valor de conteo como el número resultante de cámaras.

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 for 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 the newly created node
    return (temp);
}
 
// Stores the minimum number of
// cameras required
int cnt = 0;
 
// Utility function to find minimum
// number of cameras required to
// monitor the entire tree
int minCameraSetupUtil(Node* root)
{
    // If root is NULL
    if (root == NULL)
        return 1;
 
    int L = minCameraSetupUtil(
        root->left);
    int R = minCameraSetupUtil(
        root->right);
 
    // Both the nodes are monitored
    if (L == 1 && R == 1)
        return 2;
 
    // If one of the left and the
    // right subtree is not monitored
    else if (L == 2 || R == 2) {
        cnt++;
        return 3;
    }
 
    // If the root node is monitored
    return 1;
}
 
// Function to find the minimum number
// of cameras required to monitor
// entire tree
void minCameraSetup(Node* root)
{
    int value = minCameraSetupUtil(root);
 
    // Print the count of cameras
    cout << cnt + (value == 2 ? 1 : 0);
}
 
// Driver Code
int main()
{
    // Given Binary Tree
    Node* root = newNode(0);
    root->left = newNode(0);
    root->left->left = newNode(0);
    root->left->left->left = newNode(0);
    root->left->left->left->right = newNode(0);
 
    minCameraSetup(root);
 
    return 0;
}

Java

// Java program for the above approach
public class GFG {
    // TreeNode class
    static class Node {
        public int key;
        public Node left, right;
    };
 
    static Node newNode(int key)
    {
        Node temp = new Node();
        temp.key = key;
        temp.left = temp.right = null;
        return temp;
    }
 
    // Stores the minimum number of
    // cameras required
    static int cnt = 0;
 
    // Utility function to find minimum
    // number of cameras required to
    // monitor the entire tree
    static int minCameraSetupUtil(Node root)
    {
        // If root is NULL
        if (root == null)
            return 1;
 
        int L = minCameraSetupUtil(root.left);
        int R = minCameraSetupUtil(root.right);
 
        // Both the nodes are monitored
        if (L == 1 && R == 1)
            return 2;
 
        // If one of the left and the
        // right subtree is not monitored
        else if (L == 2 || R == 2) {
            cnt++;
            return 3;
        }
 
        // If the root node is monitored
        return 1;
    }
 
    // Function to find the minimum number
    // of cameras required to monitor
    // entire tree
    static void minCameraSetup(Node root)
    {
        int value = minCameraSetupUtil(root);
 
        // Print the count of cameras
        System.out.println(cnt + (value == 2 ? 1 : 0));
    }
 
    // Driver code
    public static void main(String[] args)
    {
        // Given Binary Tree
        Node root = newNode(0);
        root.left = newNode(0);
        root.left.left = newNode(0);
        root.left.left.left = newNode(0);
        root.left.left.left.right = newNode(0);
 
        minCameraSetup(root);
    }
}
// This code is contributed by abhinavjain194

Python3

# Python3 program for the above approach
 
# Structure for a Tree node
class Node:
     
    def __init__(self, k):
         
        self.key = k
        self.left = None
        self.right = None
 
# Stores the minimum number of
# cameras required
cnt = 0
 
# Utility function to find minimum
# number of cameras required to
# monitor the entire tree
def minCameraSetupUtil(root):
     
    global cnt
     
    # If root is None
    if (root == None):
        return 1
 
    L = minCameraSetupUtil(root.left)
    R = minCameraSetupUtil(root.right)
 
    # Both the nodes are monitored
    if (L == 1 and R == 1):
        return 2
 
    # If one of the left and the
    # right subtree is not monitored
    elif (L == 2 or R == 2):
        cnt += 1
        return 3
 
    # If the root node is monitored
    return 1
 
# Function to find the minimum number
# of cameras required to monitor
# entire tree
def minCameraSetup(root):
     
    value = minCameraSetupUtil(root)
 
    # Print the count of cameras
    print(cnt + (1 if value == 2 else 0))
 
# Driver Code
if __name__ == '__main__':
     
    # Given Binary Tree
    root = Node(0)
    root.left = Node(0)
    root.left.left = Node(0)
    root.left.left.left = Node(0)
    root.left.left.left.right = Node(0)
 
    minCameraSetup(root)
 
# This code is contributed by mohit kumar 29

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG
{
   
    // TreeNode class
    class Node {
        public int key;
        public Node left, right;
    };
 
    static Node newNode(int key)
    {
        Node temp = new Node();
        temp.key = key;
        temp.left = temp.right = null;
        return temp;
    }
 
    // Stores the minimum number of
    // cameras required
    static int cnt = 0;
 
    // Utility function to find minimum
    // number of cameras required to
    // monitor the entire tree
    static int minCameraSetupUtil(Node root)
    {
       
        // If root is NULL
        if (root == null)
            return 1;
 
        int L = minCameraSetupUtil(root.left);
        int R = minCameraSetupUtil(root.right);
 
        // Both the nodes are monitored
        if (L == 1 && R == 1)
            return 2;
 
        // If one of the left and the
        // right subtree is not monitored
        else if (L == 2 || R == 2) {
            cnt++;
            return 3;
        }
 
        // If the root node is monitored
        return 1;
    }
 
    // Function to find the minimum number
    // of cameras required to monitor
    // entire tree
    static void minCameraSetup(Node root)
    {
        int value = minCameraSetupUtil(root);
 
        // Print the count of cameras
        Console.WriteLine(cnt + (value == 2 ? 1 : 0));
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        // Given Binary Tree
        Node root = newNode(0);
        root.left = newNode(0);
        root.left.left = newNode(0);
        root.left.left.left = newNode(0);
        root.left.left.left.right = newNode(0);
 
        minCameraSetup(root);
    }
}
 
// This code is contributed by Amit Katiyar

Javascript

<script>
    // Javascript program for the above approach
     
    // TreeNode class
    class Node
    {
        constructor(key) {
           this.left = null;
           this.right = null;
           this.key = key;
        }
    }
     
    function newNode(key)
    {
        let temp = new Node(key);
        return temp;
    }
     
    // Stores the minimum number of
    // cameras required
    let cnt = 0;
  
    // Utility function to find minimum
    // number of cameras required to
    // monitor the entire tree
    function minCameraSetupUtil(root)
    {
        
        // If root is NULL
        if (root == null)
            return 1;
  
        let L = minCameraSetupUtil(root.left);
        let R = minCameraSetupUtil(root.right);
  
        // Both the nodes are monitored
        if (L == 1 && R == 1)
            return 2;
  
        // If one of the left and the
        // right subtree is not monitored
        else if (L == 2 || R == 2) {
            cnt++;
            return 3;
        }
  
        // If the root node is monitored
        return 1;
    }
  
    // Function to find the minimum number
    // of cameras required to monitor
    // entire tree
    function minCameraSetup(root)
    {
        let value = minCameraSetupUtil(root);
  
        // Print the count of cameras
        document.write(cnt + (value == 2 ? 1 : 0) + "</br>");
    }
     
    // Given Binary Tree
    let root = newNode(0);
    root.left = newNode(0);
    root.left.left = newNode(0);
    root.left.left.left = newNode(0);
    root.left.left.left.right = newNode(0);
 
    minCameraSetup(root);
 
// This code is contributed by suresh07.
</script>
Producción: 

2

 

Complejidad de Tiempo: O(N)
Espacio Auxiliar: O(H), donde H es la altura del árbol dado .

Publicación traducida automáticamente

Artículo escrito por rutvikchandla3 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *