Cuente los Nodes balanceados presentes en un árbol binario

Posted on by Rudeus Greyrat

Dado un árbol binario , la tarea es contar el número de Nodes balanceados en el árbol dado.

Los Nodes equilibrados de un árbol binario se definen como los Nodes que contienen subárboles izquierdo y derecho con su respectiva suma de valores de Node iguales.

Ejemplos:

Aporte:

                   9
                 /  \
                2   4 
               / \   \
             -1   3   0

Salida: 1
Explicación:
Solo el Node 9 contiene la suma del subárbol izquierdo = suma del subárbol derecho = 4
Por lo tanto, la salida requerida es 1.

Aporte:

                  7
                 / \
                4  10
              /  \     
            3    3
          / \     \
        0    0    -3
                  /
                 3

Salida: 3

Enfoque: la idea es recorrer recursivamente cada Node del árbol binario dado . Para cada Node, calcule la suma de los Nodes en el subárbol izquierdo y derecho y verifique si las sumas calculadas son iguales o no. Si se determina que es cierto, aumente la cuenta . Finalmente, imprima el conteo después de completar el recorrido del árbol .

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

  1. Inicialice una variable, digamos, res , para almacenar el recuento de Nodes equilibrados
  2. Calcule recursivamente la suma del subárbol izquierdo y derecho para cada Node.
  3. Compruebe si las sumas calculadas son iguales o no.
  4. Si se determina que es cierto, el Node actual está equilibrado. Por lo tanto, incremente res en 1
  5. Finalmente, imprima el valor de res después de recorrer completamente el árbol.

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

C++

// C++ program to implement
// the above 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 get the sum of left
// subtree and right subtree
int Sum(Node* root, int& res)
{
    // Base case
    if (root == NULL) {
        return 0;
    }
 
    // Store the sum of
    // left subtree
    int leftSubSum
        = Sum(root->left, res);
 
    // Store the sum of
    // right subtree
    int rightSubSum
        = Sum(root->right, res);
 
    // Check if node is balanced or not
    if (root->left and root->right
        && leftSubSum == rightSubSum)
 
        // Increase count of
        // balanced nodes
        res += 1;
 
    // Return subtree sum
    return root->data + leftSubSum
           + rightSubSum;
}
 
// Driver Code
int main()
{
 
    /*
                   9
                 /  \
                2   4
               / \   \
             -1   3   0
    */
 
    // Insert nodes in tree
    Node* root = new Node(9);
    root->left = new Node(2);
    root->left->left = new Node(-1);
    root->left->right = new Node(3);
    root->right = new Node(4);
    root->right->right = new Node(0);
 
    // Store the count of balanced nodes
    int res = 0;
    Sum(root, res);
    cout << res;
}

Java

// Java program to implement
// the above approach
class GFG{
     
static int res = 0;
   
// Structure of a
// Tree Node
static class Node
{
  int data;
  Node left;
  Node right;
  Node(int val)
  {
    data = val;
    left = right = null;
  }
};
 
// Function to get the sum of left
// subtree and right subtree
static int Sum(Node root)
{
  // Base case
  if (root == null)
  {
    return 0;
  }
 
  // Store the sum of
  // left subtree
  int leftSubSum = Sum(root.left);
 
  // Store the sum of
  // right subtree
  int rightSubSum = Sum(root.right);
 
  // Check if node is balanced or not
  if (root.left != null && root.right != null &&
      leftSubSum == rightSubSum)
 
    // Increase count of
    // balanced nodes
    res += 1;
 
  // Return subtree sum
  return root.data + leftSubSum +
         rightSubSum;
}
 
// Driver Code
public static void main(String[] args)
{
  /*
                   9
                 /  \
                2   4
               / \   \
             -1   3   0
    */
 
  // Insert nodes in tree
  Node root = new Node(9);
  root.left = new Node(2);
  root.left.left = new Node(-1);
  root.left.right = new Node(3);
  root.right = new Node(4);
  root.right.right = new Node(0);
 
  // Store the count of balanced nodes
  res = 0;
  Sum(root);
  System.out.print(res);
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python3 program to implement
# the above approach
 
# Structure of a  Tree Node
class Node:
    def __init__(self, val):
         
        self.data = val
        self.left = None
        self.right = None
 
# Function to get the sum of left
# subtree and right subtree
def Sum(root):
 
    global res
 
    # Base case
    if (root == None):
        return 0
 
    # Store the sum of
    # left subtree
    leftSubSum = Sum(root.left)
 
    # Store the sum of
    # right subtree
    rightSubSum = Sum(root.right)
 
    # Check if node is balanced or not
    if (root.left and root.right and
       leftSubSum == rightSubSum):
 
        # Increase count of
        # balanced nodes
        res += 1
 
    # Return subtree sum
    return (root.data + leftSubSum +
                        rightSubSum)
 
# Driver Code
"""
                  9
                 / \
                2   4 
               / \   \
             -1   3   0
"""
# Insert nodes in tree
root = Node(9)
root.left = Node(2)
root.left.left = Node(-1)
root.left.right = Node(3)
root.right = Node(4)
root.right.right = Node(0)
 
# Store the count of balanced nodes
global res
res = 0
Sum(root)
print(res)
 
# This code is contributed by Shivam Singh

C#

// C# program to implement
// the above approach
using System;
class GFG{
     
static int res = 0;
   
// Structure of a
// Tree Node
public class Node
{
  public int data;
  public Node left;
  public Node right;
  public Node(int val)
  {
    data = val;
    left = right = null;
  }
};
 
// Function to get the sum of left
// subtree and right subtree
static int Sum(Node root)
{
  // Base case
  if (root == null)
  {
    return 0;
  }
 
  // Store the sum of
  // left subtree
  int leftSubSum = Sum(root.left);
 
  // Store the sum of
  // right subtree
  int rightSubSum = Sum(root.right);
 
  // Check if node is balanced or not
  if (root.left != null && root.right != null &&
      leftSubSum == rightSubSum)
 
    // Increase count of
    // balanced nodes
    res += 1;
 
  // Return subtree sum
  return root.data + leftSubSum +
         rightSubSum;
}
 
// Driver Code
public static void Main(String[] args)
{
  /*
                   9
                 /  \
                2   4
               / \   \
             -1   3   0
    */
 
  // Insert nodes in tree
  Node root = new Node(9);
  root.left = new Node(2);
  root.left.left = new Node(-1);
  root.left.right = new Node(3);
  root.right = new Node(4);
  root.right.right = new Node(0);
 
  // Store the count of balanced nodes
  res = 0;
  Sum(root);
  Console.Write(res);
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
 
    // JavaScript program for the above approach
     
    let res = 0;
    
    // Structure of a Tree Node
    class Node
    {
        constructor(val) {
           this.left = null;
           this.right = null;
           this.data = val;
        }
    }
 
    // Function to get the sum of left
    // subtree and right subtree
    function Sum(root)
    {
      // Base case
      if (root == null)
      {
        return 0;
      }
 
      // Store the sum of
      // left subtree
      let leftSubSum = Sum(root.left);
 
      // Store the sum of
      // right subtree
      let rightSubSum = Sum(root.right);
 
      // Check if node is balanced or not
      if (root.left != null && root.right != null &&
          leftSubSum == rightSubSum)
 
        // Increase count of
        // balanced nodes
        res += 1;
 
      // Return subtree sum
      return root.data + leftSubSum +
             rightSubSum;
    }
     
    /*
                   9
                 /  \
                2   4
               / \   \
             -1   3   0
    */
  
    // Insert nodes in tree
    let root = new Node(9);
    root.left = new Node(2);
    root.left.left = new Node(-1);
    root.left.right = new Node(3);
    root.right = new Node(4);
    root.right.right = new Node(0);
 
    // Store the count of balanced nodes
    res = 0;
    Sum(root);
    document.write(res);
 
</script>
Producción: 

1

 

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

Publicación traducida automáticamente

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