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>
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