Recuento de Nodes cuyos hijos dan el mismo resto cuando se divide por K

Posted on by Rudeus Greyrat

Dado un árbol binario y un entero K . La tarea es contar el número de Nodes que tienen hijos que dan el mismo resto cuando se divide por K . Imprima «-1» si no existe tal Node.

Ejemplos:

Entrada:    2 K = 2
             / \
           3 5
         / / \
       7 8 6
Salida: 2
Explicación: Los hijos de 2 son 3 y 5. Ambos dan resto 1 con 2
De manera similar para 5, ambos hijos dan resto 0

Entrada: 9 K = 5
           / \
         7 8
             / \
           4 3
Salida: -1
Explicación: No hay ningún Node que tenga ambos hijos con el mismo resto con K.

 

Enfoque: Este problema se puede resolver mediante un simple recorrido del árbol binario. Siga los pasos a continuación para resolver el problema dado.

  • Atraviese el árbol binario y, para cada Node, compruebe
  • Si el Node tiene un hijo izquierdo
  • Si el Node tiene un hijo derecho
  • Si ambos niños dan el mismo resto con K .
  • Cuente todos esos Nodes e imprima su contenido al final.

A continuación se muestra la implementación del enfoque anterior.

C++

// C++ implementation to print
// the nodes having a single child
#include <bits/stdc++.h>
using namespace std;
 
// Class of the Binary Tree node
struct Node {
    int data;
    Node *left, *right;
 
    Node(int x)
    {
        data = x;
        left = right = NULL;
    }
};
 
// Function to find the nodes having both
// and both of them % K are same
int countNodes(Node* root, int& K, int count)
{
    // Base case
    if (root == NULL)
        return count;
 
    // Condition to check if the
    // node is having both child
    // and both of them % K are same
    if (root->left != NULL
        && root->right != NULL
        && root->left->data % K
            == root->right->data % K) {
 
        count++;
    }
 
    // Traversing the left child
    count = countNodes(root->left, K, count);
 
    // Traversing the right child
    count = countNodes(root->right, K, count);
    return count;
}
 
// Driver code
int main()
{
   
    // Constructing the binary tree
    Node* root = new Node(2);
    root->left = new Node(3);
    root->right = new Node(5);
    root->left->left = new Node(7);
    root->right->left = new Node(8);
    root->right->right = new Node(6);
 
    int K = 2;
 
    // Function calling
    cout << countNodes(root, K, 0);
}

Java

// Java code for the above approach
 
import java.io.*;
class Node {
    int data;
    Node left, right;
 
    Node(int data)
    {
        this.data = data;
        left = null;
        right = null;
    }
};
 
class GFG {
    // Function to find the nodes having both
    // and both of them % K are same
    static int countNodes(Node root, int K, int count)
    {
        // Base case
        if (root == null)
            return count;
 
        // Condition to check if the
        // node is having both child
        // and both of them % K are same
        if (root.left != null && root.right != null
            && (root.left.data % K
                == root.right.data % K)) {
 
            count++;
        }
 
        // Traversing the left child
        count = countNodes(root.left, K, count);
 
        // Traversing the right child
        count = countNodes(root.right, K, count);
        return count;
    }
    public static void main(String[] args)
    {
        // Driver code
 
        // Constructing the binary tree
        Node root = new Node(2);
        root.left = new Node(3);
        root.right = new Node(5);
        root.left.left = new Node(7);
        root.right.left = new Node(8);
        root.right.right = new Node(6);
 
        int K = 2;
 
        // Function calling
 
        System.out.println(countNodes(root, K, 0));
    }
}
//This code is contributed by Potta Lokesh

Python3

# Python code for the above approach
class Node:
    def __init__(self, data):
        self.data = data;
        self.left = None;
        self.right = None;
 
# Function to find the Nodes having both
# and both of them % K are same
def countNodes(root, K, count):
   
    # Base case
    if (root == None):
        return count;
 
    # Condition to check if the
    # Node is having both child
    # and both of them % K are same
    if (root.left != None and root.right != None and (root.left.data % K == root.right.data % K)):
 
        count += 1;
     
    # Traversing the left child
    count = countNodes(root.left, K, count);
 
    # Traversing the right child
    count = countNodes(root.right, K, count);
    return count;
 
if __name__ == '__main__':
    # Driver code
 
    # Constructing the binary tree
    root =  Node(2);
    root.left =  Node(3);
    root.right =  Node(5);
    root.left.left =  Node(7);
    root.right.left =  Node(8);
    root.right.right =  Node(6);
 
    K = 2;
 
    # Function calling
    print(countNodes(root, K, 0));
 
# This code is contributed by umadevi9616

C#

// C# code for the above approach
using System;
using System.Collections.Generic;
 
class Node {
  public int data;
  public Node left, right;
 
  public Node(int data)
  {
    this.data = data;
    left = null;
    right = null;
  }
};
 
public class GFG
{
 
  // Function to find the nodes having both
  // and both of them % K are same
  static int countNodes(Node root, int K, int count)
  {
 
    // Base case
    if (root == null)
      return count;
 
    // Condition to check if the
    // node is having both child
    // and both of them % K are same
    if (root.left != null && root.right != null
        && (root.left.data % K
            == root.right.data % K)) {
 
      count++;
    }
 
    // Traversing the left child
    count = countNodes(root.left, K, count);
 
    // Traversing the right child
    count = countNodes(root.right, K, count);
    return count;
  }
  public static void Main(String[] args)
  {
    // Driver code
 
    // Constructing the binary tree
    Node root = new Node(2);
    root.left = new Node(3);
    root.right = new Node(5);
    root.left.left = new Node(7);
    root.right.left = new Node(8);
    root.right.right = new Node(6);
 
    int K = 2;
 
    // Function calling
 
    Console.WriteLine(countNodes(root, K, 0));
  }
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
// Javascript code for the above approach
class Node {
 
    constructor(data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
};
 
// Function to find the nodes having both
// and both of them % K are same
function countNodes(root, K, count)
{
 
    // Base case
    if (root == null)
        return count;
 
    // Condition to check if the
    // node is having both child
    // and both of them % K are same
    if (root.left != null && root.right != null
        && (root.left.data % K
            == root.right.data % K)) {
 
        count++;
    }
 
    // Traversing the left child
    count = countNodes(root.left, K, count);
 
    // Traversing the right child
    count = countNodes(root.right, K, count);
    return count;
}
 
// Driver code
 
// Constructing the binary tree
let root = new Node(2);
root.left = new Node(3);
root.right = new Node(5);
root.left.left = new Node(7);
root.right.left = new Node(8);
root.right.right = new Node(6);
 
let K = 2;
 
// Function calling
 
document.write(countNodes(root, K, 0));
 
// This code is contributed by Saurabh Jaiswal
</script>
Producción

2

Complejidad temporal: O(N)
Espacio auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por Code_r 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 *