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