Suma de bit a bit Y de la suma de todos los Nodes hoja y no hoja para cada nivel de un árbol binario

Dado un árbol binario que consta de N Nodes, la tarea es encontrar la suma de Bitwise AND de la suma de todos los Nodes hoja y la suma de todos los Nodes no hoja para cada nivel en el árbol dado.

Ejemplos:

Entrada: A continuación se muestra el árbol dado:
               5     
             / \    
           3 9   
          / \      
        6 4   
         \    
         7
Salida: 5
Explicación:

Para el Nivel 1: suma de Nodes hoja = 0, suma de Nodes no hoja = 5. Entonces, 0&5 = 0.    
Para Nivel 2: suma de Nodes hoja = 9, suma de Nodes no hoja = 3. Entonces, 9&3 = 1.    
Para Nivel 3: suma de Nodes hoja = 4, suma de Nodes no hoja = 6. Por lo tanto, 6 y 4 = 4.    
Para el nivel 4: suma de Nodes hoja = 7, suma de Nodes no hoja = 0. Por lo tanto, 0 y 7 = 0.    
Por lo tanto, el total la suma es 0 + 1 + 4 + 0 = 5.

Entrada: Debajo está el árbol dado:
                 4     
               / \    
              9 3       
                  / \      
                5 3
Salida: 1
Explicación:
Para el Nivel 1: suma de Nodes hoja = 0, suma de Nodes no hoja = 4. Entonces, 0&4 = 0     
Para Nivel 2: hoja suma de Nodes = 9, suma de Nodes no hoja = 3. Entonces, 9&3 = 1     
Para el nivel 3: suma de Nodes hoja = 8, suma de Nodes no hoja = 0. Entonces, 8&0 = 0     
Por lo tanto, la suma total es 0 + 1 + 0 = 1 

Enfoque: La idea para resolver el problema anterior es realizar el recorrido de orden de niveles del árbol. Mientras realiza el recorrido, procese los Nodes de diferentes niveles por separado y para cada nivel que se procese, encuentre la suma de los Nodes de hoja y los Nodes de no hoja para cada nivel. Siga los pasos a continuación para resolver el problema:

  • Inicialice una cola Q y empuje el Node raíz hacia ella e inicialice ans como 0 para almacenar la respuesta requerida.
  • Realice los siguientes pasos hasta que Q no esté vacío :
    • Inicialice leafSum como 0 y nonLeafSum como 0 para almacenar la suma de los Nodes hoja y Nodes no hoja en el nivel actual, respectivamente.
    • Encuentre el tamaño actual de la cola Q y sea L .
    • Iterar sobre el rango [0, L] y hacer lo siguiente:
      • Extraiga el Node de la cola .
      • Si el Node emergente es un Node de hoja, agregue el valor a leafSum; de lo contrario, agréguelo a nonLeafSum .
      • Empuje el hijo izquierdo y derecho del Node emergente actual en la cola si existen.
    • Para el nivel actual, agregue el AND bit a bit de leafSum y nonLeafSum a la variable ans .
  • Después de completar los pasos anteriores, imprima el valor de ans como resultado.

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

C++

// C++ program for given approach
#include<bits/stdc++.h>
using namespace std;
 
// Structure of a Binary tree node
struct TreeNode
{
  int val;
  TreeNode *left,*right;
   
  // Helper function to allocate
  // a new node with the given data
  // and left and right pointers as None
    TreeNode(int x = 0)
    {
        val = x;
        left = NULL;
        right = NULL;
   }
};
 
// Function to calculate the sum of
// bitwise AND of the sum of all leaf
// nodes and non-leaf nodes for each level
int findSum(TreeNode *root){
 
    // Initialize a queue and
    // append root to it
    queue<TreeNode*> que;
 
    que.push(root);
     
  // Store the required answer
    int ans = 0;
    while (que.size())
    {
 
        // Stores the sum of leaf nodes
        // at the current level
        int leaf = 0;
 
        // Stores the sum of non-leaf
        // nodes at the current level
        int nonleaf = 0;
 
        // Get the size of the queue
        int length = que.size();
 
        // Iterate for all the nodes
        // in the queue currently
        while (length)
        {
 
            // Dequeue a node from queue
            auto temp = que.front();
            que.pop();
 
            // Check if the node is a
            // leaf node
            if (!temp->left && !temp->right)
               
                // If true, update the
                // leaf node sum
                leaf += temp->val;
           
            // Otherwise, update the
            // non-leaf node sum
            else
                nonleaf += temp->val;
 
            // Enqueue left and right
            // children of removed node
            if (temp->left)
                que.push(temp->left);
            if (temp->right)
                que.push(temp->right);
 
            length -= 1;
        }
 
        // Update the answer
        ans += leaf & nonleaf;
      }
 
    // Return the answer
    return ans;
}
 
// Driver Code
int main()
{
   
  // Given Tree
  TreeNode *root = new TreeNode(5);
  root->left = new TreeNode(3);
  root->right = new TreeNode(9);
  root->left->left = new TreeNode(6);
  root->left->right = new TreeNode(4);
  root->left->left->right = new TreeNode(7);
   
  // Function Call
  cout<<findSum(root);
}
 
// This code is contributed by mohit kumar 29.

Java

// Java program for given approach
import java.util.*;
class GFG
{
 
// Structure of a Binary tree node
static class TreeNode
{
  int val;
  TreeNode left,right;
   
  // Helper function to allocate
  // a new node with the given data
  // and left and right pointers as None
    TreeNode(int x)
    {
        val = x;
        left = null;
        right = null;
   }
};
 
// Function to calculate the sum of
// bitwise AND of the sum of all leaf
// nodes and non-leaf nodes for each level
static int findSum(TreeNode root)
{
 
    // Initialize a queue and
    // append root to it
    Queue<TreeNode> que = new LinkedList<>();
 
    que.add(root);
     
  // Store the required answer
    int ans = 0;
    while (que.size() > 0)
    {
 
        // Stores the sum of leaf nodes
        // at the current level
        int leaf = 0;
 
        // Stores the sum of non-leaf
        // nodes at the current level
        int nonleaf = 0;
 
        // Get the size of the queue
        int length = que.size();
 
        // Iterate for all the nodes
        // in the queue currently
        while (length>0)
        {
 
            // Dequeue a node from queue
            TreeNode temp = que.peek();
            que.remove();
 
            // Check if the node is a
            // leaf node
            if (temp.left == null && temp.right == null)
               
                // If true, update the
                // leaf node sum
                leaf += temp.val;
           
            // Otherwise, update the
            // non-leaf node sum
            else
                nonleaf += temp.val;
 
            // Enqueue left and right
            // children of removed node
            if (temp.left != null)
                que.add(temp.left);
            if (temp.right != null)
                que.add(temp.right);
 
            length -= 1;
        }
 
        // Update the answer
        ans += leaf & nonleaf;
      }
 
    // Return the answer
    return ans;
}
 
// Driver Code
public static void main(String[] args)
{
   
  // Given Tree
  TreeNode root = new TreeNode(5);
  root.left = new TreeNode(3);
  root.right = new TreeNode(9);
  root.left.left = new TreeNode(6);
  root.left.right = new TreeNode(4);
  root.left.left.right = new TreeNode(7);
   
  // Function Call
  System.out.print(findSum(root));
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python program for the above approach
 
# Structure of a Binary tree node
class TreeNode:
 
    # Helper function to allocate
    # a new node with the given data
    # and left and right pointers as None
    def __init__(self, val = 0, left = None, right = None):
        self.val = val
        self.left = left
        self.right = right
 
# Function to calculate the sum of
# bitwise AND of the sum of all leaf
# nodes and non-leaf nodes for each level
def findSum(root):
 
    # Initialize a queue and
    # append root to it
    que = [root]
 
    # Store the required answer
    ans = 0
 
    while (len(que)):
 
        # Stores the sum of leaf nodes
        # at the current level
        leaf = 0
 
        # Stores the sum of non-leaf
        # nodes at the current level
        nonleaf = 0
 
        # Get the size of the queue
        length = len(que)
 
        # Iterate for all the nodes
        # in the queue currently
        while length:
 
            # Dequeue a node from queue
            temp = que.pop(0)
 
            # Check if the node is a
            # leaf node
            if not temp.left and not temp.right:
 
                # If true, update the
                # leaf node sum
                leaf += temp.val
 
            # Otherwise, update the
            # non-leaf node sum
            else:
                nonleaf += temp.val
 
            # Enqueue left and right
            # children of removed node
            if temp.left:
                que.append(temp.left)
            if temp.right:
                que.append(temp.right)
 
            length -= 1
 
        # Update the answer
        ans += leaf & nonleaf
 
    # Return the answer
    return ans
 
 
# Driver Code
 
# Given Tree
root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(9)
root.left.left = TreeNode(6)
root.left.right = TreeNode(4)
root.left.left.right = TreeNode(7)
 
# Function Call
print(findSum(root))

C#

// C# program for given approach
 
using System;
using System.Collections.Generic;
 
// Structure of a Binary tree node
class GFG{
 
class TreeNode
{
  public int val;
  public TreeNode left,right;
};
   
  // Helper function to allocate
  // a new node with the given data
  // and left and right pointers as None
  static TreeNode newNode(int x)
    {
        TreeNode temp = new TreeNode();
        temp.val = x;
        temp.left = null;
        temp.right = null;
        return temp;
   }
 
// Function to calculate the sum of
// bitwise AND of the sum of all leaf
// nodes and non-leaf nodes for each level
static int findSum(TreeNode root){
 
    // Initialize a queue and
    // append root to it
    Queue<TreeNode> que =new Queue<TreeNode>();
 
    que.Enqueue(root);
     
  // Store the required answer
    int ans = 0;
    while (que.Count>0)
    {
 
        // Stores the sum of leaf nodes
        // at the current level
        int leaf = 0;
 
        // Stores the sum of non-leaf
        // nodes at the current level
        int nonleaf = 0;
 
        // Get the size of the queue
        int length = que.Count;
 
        // Iterate for all the nodes
        // in the queue currently
        while (length>0)
        {
 
            // Dequeue a node from queue
            TreeNode temp = que.Peek();
            que.Dequeue();
 
            // Check if the node is a
            // leaf node
            if (temp.left == null && temp.right==null)
               
                // If true, update the
                // leaf node sum
                leaf += temp.val;
           
            // Otherwise, update the
            // non-leaf node sum
            else
                nonleaf += temp.val;
 
            // Enqueue left and right
            // children of removed node
            if (temp.left!=null)
                que.Enqueue(temp.left);
            if (temp.right != null)
                que.Enqueue(temp.right);
 
            length -= 1;
        }
 
        // Update the answer
        ans += (leaf & nonleaf);
      }
 
    // Return the answer
    return ans;
}
 
// Driver Code
public static void Main()
{
   
  // Given Tree
  TreeNode root = newNode(5);
  root.left = newNode(3);
  root.right = newNode(9);
  root.left.left = newNode(6);
  root.left.right = newNode(4);
  root.left.left.right = newNode(7);
   
  // Function Call
  Console.WriteLine(findSum(root));
}
}
 
// This code is contributed by bgangwar59.

Javascript

<script>
 
// Javascript program for given approach
 
// Structure of a Binary tree node
class TreeNode
{
     
    // Helper function to allocate
    // a new node with the given data
    // and left and right pointers as None
    constructor(x)
    {
        this.val = x;
        this.left = null;
        this.right = null;
    }
}
 
// Function to calculate the sum of
// bitwise AND of the sum of all leaf
// nodes and non-leaf nodes for each level
function findSum(root)
{
     
    // Initialize a queue and
    // append root to it
    let que = [];
  
    que.push(root);
      
    // Store the required answer
    let ans = 0;
    while (que.length > 0)
    {
         
        // Stores the sum of leaf nodes
        // at the current level
        let leaf = 0;
  
        // Stores the sum of non-leaf
        // nodes at the current level
        let nonleaf = 0;
  
        // Get the size of the queue
        let length = que.length;
  
        // Iterate for all the nodes
        // in the queue currently
        while (length > 0)
        {
             
            // Dequeue a node from queue
            let temp = que.shift();
             
            // Check if the node is a
            // leaf node
            if (temp.left == null &&
                temp.right == null)
                
                // If true, update the
                // leaf node sum
                leaf += temp.val;
            
            // Otherwise, update the
            // non-leaf node sum
            else
                nonleaf += temp.val;
  
            // Enqueue left and right
            // children of removed node
            if (temp.left != null)
                que.push(temp.left);
            if (temp.right != null)
                que.push(temp.right);
  
            length -= 1;
        }
         
        // Update the answer
        ans += leaf & nonleaf;
    }
     
    // Return the answer
    return ans;
}
 
// Driver Code
 
// Given Tree
let root = new TreeNode(5);
root.left = new TreeNode(3);
root.right = new TreeNode(9);
root.left.left = new TreeNode(6);
root.left.right = new TreeNode(4);
root.left.left.right = new TreeNode(7);
 
// Function Call
document.write(findSum(root));
 
// This code is contributed by unknown2108
 
</script>
Producción: 

5

 

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

Publicación traducida automáticamente

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