Recuento de Nodes con un promedio de subárbol izquierdo de al menos K en un árbol binario dado

Posted on by Rudeus Greyrat

Dado un árbol binario y un número K, la tarea es contar el número de Nodes que tienen el promedio de los valores en su subárbol izquierdo mayor o igual a K.

Ejemplos:

Entrada:  K=5
Árbol:    
               2
           / \
        5 4
      / \ / \
   5 6 6 2
    \ /
    5 4
Salida: 3
Explicación:  
               2 ——– nivel 0
           / \                        
        5 4 ——– nivel 1
      / \ / \                    
   5 6 6 2 ——– nivel 2
    \ /                          
    5 4 ——– nivel 3

Promedio del subárbol izquierdo izquierdo para el Node raíz 2 = (5+5+5) / 3 = 5
Promedio del subárbol izquierdo izquierdo para el Node 4 en el nivel 1 = (6+4) / 2 = 5
Promedio del subárbol izquierdo izquierdo para el Node 5 en el nivel 1 = (5+5) / 2 = 5
Entonces, estos 3 Nodes satisfacen las condiciones dadas.

Entrada: K = 4             ,
Árbol         :             1/2/3/4       Salida
                :
              1

 

Enfoque: siga los pasos a continuación para resolver este problema:

  1. Cree una variable global ans para almacenar la respuesta e inicialícela con 0 .
  2. Cree una función countHelper que aceptará un Node de árbol y el número entero K como parámetro, y devolverá un par de la suma de Nodes y el número de Nodes en el subárbol de ese Node.
  3. Ahora, pase el Node raíz y K en la llamada inicial de esta función.
  4. En cada llamada de esta función recursiva:
    1. Compruebe si el Node actual es un Node hoja o no. Si es un Node hoja, simplemente devuelva {0, 0} ya que tanto la suma como el número de Nodes debajo de este Node es 0 .
    2. Ahora, llame a los subárboles izquierdo y derecho.
    3. Compruebe si para el Node actual, (la suma del subárbol izquierdo y derecho/número de Nodes en el subárbol izquierdo y derecho)>=K , si se incrementa en 1 .
  5. Después de que finalice la función recursiva, imprima ans .

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

C++

// C++ code for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Structure of a tree node
class Node {
public:
    int data;
    Node *left, *right;
    Node(int d)
    {
        data = d;
        left = right = NULL;
    }
};
 
// Global variable to store the node count
int ans = 0;
 
// Function to count the nodes in a tree
// with average of all left nodes
// greater than or equal to K .
pair<int, int> countHelper(Node* root,
                           int K)
{
 
    // For leaf Node
    if (!root->left and !root->right) {
        return { root->data, 1 };
    }
 
    pair<int, int> left = { 0, 0 },
                   right = { 0, 0 };
 
    // For left subtree
    if (root->left) {
        left = countHelper(root->left, K);
    }
 
    // For right subtree
    if (root->right) {
        right = countHelper(root->right, K);
    }
    if (left.second != 0
        and left.first / left.second >= K) {
        ans += 1;
    }
 
    return { left.first + right.first + root->data,
             left.second + right.second + 1 };
}
 
// Function to call the initial
// instance of function countHelper
void countNodes(Node* root, int K)
{
    countHelper(root, K);
    cout << ans;
}
 
// Driver Code
int main()
{
    // Given Tree
    Node* root = new Node(2);
    root->left = new Node(5);
    root->right = new Node(4);
    root->left->left = new Node(5);
    root->left->right = new Node(6);
    root->right->left = new Node(6);
    root->right->right = new Node(2);
    root->left->left->right = new Node(5);
    root->right->left->left = new Node(4);
 
    int K = 5;
 
    countNodes(root, K);
    return 0;
}

Java

// Java code for the above approach
import java.util.*;
 
class GFG{
 
static class pair
{
    int first, second;
    public pair(int first, int second) 
    {
        this.first = first;
        this.second = second;
    }   
}
   
// Structure of a tree node
static class Node {
    int data;
    Node left, right;
    Node(int d)
    {
        data = d;
        left = right = null;
    }
};
 
// Global variable to store the node count
static int ans = 0;
 
// Function to count the nodes in a tree
// with average of all left nodes
// greater than or equal to K .
static pair countHelper(Node root,
                           int K)
{
 
    // For leaf Node
    if (root.left==null && root.right==null) {
        return new pair( root.data, 1 );
    }
 
    pair left = new pair( 0, 0 ),
                   right = new pair( 0, 0 );
 
    // For left subtree
    if (root.left!=null) {
        left = countHelper(root.left, K);
    }
 
    // For right subtree
    if (root.right!=null) {
        right = countHelper(root.right, K);
    }
    if (left.second != 0
        && left.first / left.second >= K) {
        ans += 1;
    }
 
    return new pair( left.first + right.first + root.data,
             left.second + right.second + 1 );
}
 
// Function to call the initial
// instance of function countHelper
static void countNodes(Node root, int K)
{
    countHelper(root, K);
    System.out.print(ans);
}
 
// Driver Code
public static void main(String[] args)
{
   
    // Given Tree
    Node root = new Node(2);
    root.left = new Node(5);
    root.right = new Node(4);
    root.left.left = new Node(5);
    root.left.right = new Node(6);
    root.right.left = new Node(6);
    root.right.right = new Node(2);
    root.left.left.right = new Node(5);
    root.right.left.left = new Node(4);
 
    int K = 5;
 
    countNodes(root, K);
}
}
 
// This code is contributed by shikhasingrajput

Python3

# Python code for the above approach
class pair:
    def __init__(self, first, second):
        self.first = first;
        self.second = second;
 
# Structure of a tree node
class Node:
    def __init__(self, d):
        self.data = d;
        self.left = self.right = None;
 
# Global variable to store the node count
ans = 0;
 
# Function to count the nodes in a tree
# with average of all left nodes
# greater than or equal to K .
def countHelper(root, K):
 
    # For leaf Node
    if (root.left == None and root.right == None):
        return pair(root.data, 1);
 
    left = pair(0, 0)
    right = pair(0, 0)
 
    # For left subtree
    if (root.left != None):
        left = countHelper(root.left, K);
 
    # For right subtree
    if (root.right != None):
        right = countHelper(root.right, K);
     
    if (left.second != 0 and left.first / left.second >= K):
        global ans;
        ans += 1;
 
    return pair(left.first + right.first + root.data, left.second + right.second + 1);
 
# Function to call the initial
# instance of function countHelper
def countNodes(root, K):
    countHelper(root, K);
    print(ans);
 
# Driver Code
# Given Tree
root = Node(2);
root.left = Node(5);
root.right = Node(4);
root.left.left = Node(5);
root.left.right = Node(6);
root.right.left = Node(6);
root.right.right = Node(2);
root.left.left.right = Node(5);
root.right.left.left = Node(4);
 
K = 5;
 
countNodes(root, K);
 
# This code is contributed by Saurabh Jaiswal.

C#

// C# code for the above approach
using System;
using System.Collections.Generic;
 
public class GFG{
 
  class pair
  {
    public int first, second;
    public pair(int first, int second) 
    {
      this.first = first;
      this.second = second;
    }   
  }
 
  // Structure of a tree node
  class Node {
    public int data;
    public Node left, right;
    public Node(int d)
    {
      data = d;
      left = right = null;
    }
  };
 
  // Global variable to store the node count
  static int ans = 0;
 
  // Function to count the nodes in a tree
  // with average of all left nodes
  // greater than or equal to K .
  static pair countHelper(Node root,
                          int K)
  {
 
    // For leaf Node
    if (root.left==null && root.right==null) {
      return new pair( root.data, 1 );
    }
 
    pair left = new pair( 0, 0 ),
    right = new pair( 0, 0 );
 
    // For left subtree
    if (root.left!=null) {
      left = countHelper(root.left, K);
    }
 
    // For right subtree
    if (root.right!=null) {
      right = countHelper(root.right, K);
    }
    if (left.second != 0
        && left.first / left.second >= K) {
      ans += 1;
    }
 
    return new pair( left.first + right.first + root.data,
                    left.second + right.second + 1 );
  }
 
  // Function to call the initial
  // instance of function countHelper
  static void countNodes(Node root, int K)
  {
    countHelper(root, K);
    Console.Write(ans);
  }
 
  // Driver Code
  public static void Main(String[] args)
  {
 
    // Given Tree
    Node root = new Node(2);
    root.left = new Node(5);
    root.right = new Node(4);
    root.left.left = new Node(5);
    root.left.right = new Node(6);
    root.right.left = new Node(6);
    root.right.right = new Node(2);
    root.left.left.right = new Node(5);
    root.right.left.left = new Node(4);
 
    int K = 5;
 
    countNodes(root, K);
  }
}
 
// This code is contributed by shikhasingrajput

Javascript

<script>
// Javascript code for the above approach
 
 
class pair {
    constructor(first, second) {
        this.first = first;
        this.second = second;
    }
}
 
// Structure of a tree node
class Node {
 
    constructor(d) {
        this.data = d;
        this.left = this.right = null;
    }
};
 
// Global variable to store the node count
let ans = 0;
 
// Function to count the nodes in a tree
// with average of all left nodes
// greater than or equal to K .
function countHelper(root, K) {
 
    // For leaf Node
    if (root.left == null && root.right == null) {
        return new pair(root.data, 1);
    }
 
    let left = new pair(0, 0),
        right = new pair(0, 0);
 
    // For left subtree
    if (root.left != null) {
        left = countHelper(root.left, K);
    }
 
    // For right subtree
    if (root.right != null) {
        right = countHelper(root.right, K);
    }
    if (left.second != 0
        && left.first / left.second >= K) {
        ans += 1;
    }
 
    return new pair(left.first + right.first + root.data, left.second + right.second + 1);
}
 
// Function to call the initial
// instance of function countHelper
function countNodes(root, K) {
    countHelper(root, K);
    document.write(ans);
}
 
// Driver Code
// Given Tree
let root = new Node(2);
root.left = new Node(5);
root.right = new Node(4);
root.left.left = new Node(5);
root.left.right = new Node(6);
root.right.left = new Node(6);
root.right.right = new Node(2);
root.left.left.right = new Node(5);
root.right.left.left = new Node(4);
 
let K = 5;
 
countNodes(root, K);
 
// This code is contributed by Saurabh Jaiswal
</script>
Producción

3

Complejidad de Tiempo: O(N) donde N es el número de Nodes en el árbol
Espacio Auxiliar: O(N)

Publicación traducida automáticamente

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