Encuentre Nodes cuyos hijos tengan el mismo módulo con K

Posted on by Rudeus Greyrat

Dado un árbol binario y un entero K , la tarea es imprimir todos los Nodes que tienen hijos con el mismo resto cuando se divide por K. Imprima » -1 » si no existe tal Node.
Ejemplos :

Entrada : K = 2

           2

          / \

         3 5

        / / \

       7 8 6

Salida : 2, 5
Explicación : Hijos de 2 = 3 y 5. Ambos dan resto 1 con 2, De manera similar para 5, ambos hijos dan resto 0

Entrada : K = 5

          9

         / \

        7 8

           / \

          4 3

Salida : -1
Explicación : No hay ningún Node que tenga ambos hijos con el mismo resto con K.

 

Enfoque : la tarea se puede resolver mediante una búsqueda en profundidad . 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
  • Almacene todos esos Nodes en un vector 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;
    }
};
 
vector<int> listOfNodes;
 
// Function to find the nodes
// having both child
// and both of them % K are same
void countNodes(Node* root, int& K)
{
    // Base case
    if (root == NULL)
        return;
 
    // 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) {
 
        listOfNodes.push_back(root->data);
    }
 
    // Traversing the left child
    countNodes(root->left, K);
 
    // Traversing the right child
    countNodes(root->right, K);
}
 
// 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
    countNodes(root, K);
 
    // Condition to check if there is
    // no such node having single child
    if (listOfNodes.size() == 0)
        printf("-1");
    else {
        for (int value : listOfNodes) {
            cout << (value) << endl;
        }
    }
}

Java

// Java implementation to print
// the nodes having a single child
import java.util.*;
 
class GFG{
 
// Class of the Binary Tree node
static class Node {
    int data;
    Node left, right;
 
    Node(int x)
    {
        data = x;
        left = right = null;
    }
};
 
static Vector<Integer> listOfNodes = new Vector<Integer>();
 
// Function to find the nodes
// having both child
// and both of them % K are same
static void countNodes(Node root, int K)
{
    // Base case
    if (root == null)
        return;
 
    // 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) {
 
        listOfNodes.add(root.data);
    }
 
    // Traversing the left child
    countNodes(root.left, K);
 
    // Traversing the right child
    countNodes(root.right, K);
}
 
// Driver code
public static void main(String[] args)
{
    // 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
    countNodes(root, K);
 
    // Condition to check if there is
    // no such node having single child
    if (listOfNodes.size() == 0)
        System.out.printf("-1");
    else {
        for (int value : listOfNodes) {
            System.out.print((value) +"\n");
        }
    }
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python code for the above approach
 
# Class of the Binary Tree node
class Node:
    def __init__(self, x):
        self.data = x
        self.left = self.right = None
 
listOfNodes = []
 
# Function to find the nodes
# having both child
# and both of them % K are same
def countNodes(root, K):
 
    # Base case
    if (root == None):
        return 0
 
    # 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):
 
        listOfNodes.append(root.data)
 
    # Traversing the left child
    countNodes(root.left, K)
 
    # Traversing the right child
    countNodes(root.right, K)
 
 
# 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
countNodes(root, K)
 
# Condition to check if there is
# no such node having single child
if (len(listOfNodes) == 0):
    print("-1")
else:
    for value in listOfNodes:
        print(value)
 
# This code is contributed by Saurabh Jaiswal

C#

// C# implementation to print
// the nodes having a single child
using System;
using System.Collections.Generic;
 
public class GFG{
 
  // Class of the Binary Tree node
  class Node {
    public int data;
    public Node left, right;
 
    public Node(int x)
    {
      data = x;
      left = right = null;
    }
  };
 
  static List<int> listOfNodes = new List<int>();
 
  // Function to find the nodes
  // having both child
  // and both of them % K are same
  static void countNodes(Node root, int K)
  {
    // Base case
    if (root == null)
      return;
 
    // 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) {
 
      listOfNodes.Add(root.data);
    }
 
    // Traversing the left child
    countNodes(root.left, K);
 
    // Traversing the right child
    countNodes(root.right, K);
  }
 
  // Driver code
  public static void Main(String[] args)
  {
    // 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
    countNodes(root, K);
 
    // Condition to check if there is
    // no such node having single child
    if (listOfNodes.Count == 0)
      Console.Write("-1");
    else {
      foreach (int values in listOfNodes) {
        Console.Write((values) +"\n");
      }
    }
  }
}
 
// This code is contributed by shikhasingrajput

Javascript

<script>
      // JavaScript code for the above approach
 
      // Class of the Binary Tree node
      class Node
      {
          constructor(x)
          {
              this.data = x;
              this.left = this.right = null;
          }
      };
 
      let listOfNodes = [];
 
      // Function to find the nodes
      // having both child
      // and both of them % K are same
      function countNodes(root, K)
      {
       
          // Base case
          if (root == null)
              return 0;
 
          // 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) {
 
              listOfNodes.push(root.data);
          }
 
          // Traversing the left child
          countNodes(root.left, K);
 
          // Traversing the right child
          countNodes(root.right, K);
      }
 
      // 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
      countNodes(root, K);
 
      // Condition to check if there is
      // no such node having single child
      if (listOfNodes.length == 0)
          document.write("-1");
      else {
          for (let value of listOfNodes) {
              document.write((value) + "<br>");
          }
      }
 
     // This code is contributed by Potta Lokesh
  </script>
Producción

2
5

Complejidad de Tiempo : 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 *