Dado un árbol N-ario con raíz en 1, la tarea es encontrar la diferencia entre la suma de los Nodes en el nivel impar y la suma de los Nodes en el nivel par.
Ejemplos:
Entrada:
4
/ | \
2 3 -5
/ \ / \
-1 3 -2 6
Salida: 10
Explicación:
Suma de Nodes en niveles pares = 2 + 3 + (-5) = 0
Suma de Nodes en niveles impares = 4 + (-1) + 3 + (-2) + 6 = 10
Por lo tanto, la diferencia requerida es 10.Entrada:
1
/ | \
2 -1 3
/ \ \
4 5 8
/ / | \
2 6 12 7Salida: -13
Planteamiento: Para resolver el problema, la idea es encontrar las respectivas sumas de los Nodes en los niveles pares e impares utilizando Level Order Traversal y calcular la diferencia entre ellos. Siga los pasos a continuación para resolver el problema:
- Inicialice una cola para almacenar Nodes y sus respectivos niveles.
- Inicialice las variables evenSum y oddSum para almacenar la suma de los Nodes en los niveles par e impar respectivamente.
- Empuje la raíz del árbol N-ario junto con su nivel correspondiente, es decir, 1, en la cola .
- Ahora, itere y repita los siguientes pasos hasta que la Cola se vacíe:
- Pop los Nodes de la cola. Almacene el nivel del Node emergente en una variable, digamos currentLevel.
- Si currentLevel es par , agregue el valor del Node a evenSum . De lo contrario, agregue a oddSum .
- Empuje a todos sus elementos secundarios a la cola y establezca sus respectivos niveles como currentLevel + 1 .
- Una vez que se completen los pasos anteriores, calcule e imprima la diferencia entre oddSum y evenSum .
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 node // of an n-ary tree struct Node { int val; vector<Node*> children; }; // Function to create a // new tree node Node* newNode(int val) { Node* temp = new Node; temp->val = val; return temp; } // Function to find the difference // between of sums node values of // odd and even levels in an N-ary tree int evenOddLevelDifference(Node* root) { // Store the sums of nodes at // even and odd levels int evenSum = 0, oddSum = 0; // Initialize a queue to store // pair of node and level queue<pair<Node*, int> > q; // Push the root into the // queue with level 1 q.push({ root, 1 }); // Iterate all levels // of tree are traversed while (!q.empty()) { // Store the node at the // front of the queue pair<Node*, int> currNode = q.front(); // Pop the front node q.pop(); // Store the current level int currLevel = currNode.second; // Store the current node value int currVal = currNode.first->val; // If current node // level is odd if (currLevel % 2) // Add to odd sum oddSum += currVal; else // Add to even sum evenSum += currVal; // Push all the children of current node // with increasing current level by 1 for (auto child : currNode.first->children) { q.push({ child, currLevel + 1 }); } } // Return the difference return (oddSum - evenSum); } // Driver Code int main() { // Create the N-ary Tree Node* root = newNode(4); root->children.push_back(newNode(2)); root->children.push_back(newNode(3)); root->children.push_back(newNode(-5)); root->children[0]->children.push_back(newNode(-1)); root->children[0]->children.push_back(newNode(3)); root->children[2]->children.push_back(newNode(-2)); root->children[2]->children.push_back(newNode(6)); cout << evenOddLevelDifference(root); return 0; }
Java
// Java program to implement // the above approach import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; class GFG{ // Structure of a node // of an n-ary tree static class Node { int val; ArrayList<Node> children; public Node(int val) { this.val = val; this.children = new ArrayList<Node>(); } }; static class Pair { Node first; int second; public Pair(Node node, int val) { this.first = node; this.second = val; } } // Function to find the difference // between of sums node values of // odd and even levels in an N-ary tree static int evenOddLevelDifference(Node root) { // Store the sums of nodes at // even and odd levels int evenSum = 0, oddSum = 0; // Initialize a queue to store // pair of node and level Queue<Pair> q = new LinkedList<>(); // Push the root into the // queue with level 1 q.add(new Pair(root, 1)); // Iterate all levels // of tree are traversed while (!q.isEmpty()) { // Store the node at the // front of the queue Pair currNode = q.poll(); // Store the current level int currLevel = currNode.second; // Store the current node value int currVal = currNode.first.val; // If current node // level is odd if (currLevel % 2 == 1) // Add to odd sum oddSum += currVal; else // Add to even sum evenSum += currVal; // Push all the children of current node // with increasing current level by 1 for(Node child : currNode.first.children) { q.add(new Pair(child, currLevel + 1)); } } // Return the difference return (oddSum - evenSum); } // Driver Code public static void main(String[] args) { // Create the N-ary Tree Node root = new Node(4); root.children.add(new Node(2)); root.children.add(new Node(3)); root.children.add(new Node(-5)); root.children.get(0).children.add(new Node(-1)); root.children.get(0).children.add(new Node(3)); root.children.get(2).children.add(new Node(-2)); root.children.get(2).children.add(new Node(6)); System.out.println(evenOddLevelDifference(root)); } } // This code is contributed by sanjeev2552
Python3
# Python3 program to implement # the above approach # Structure of a node # of an n-ary tree class Node: def __init__(self, val): self.val = val self.children = [] # Function to create a # new tree node def newNode(val): temp = Node(val) return temp # Function to find the difference # between of sums node values of # odd and even levels in an N-ary tree def evenOddLevelDifference(root): # Store the sums of nodes at # even and odd levels evenSum = 0 oddSum = 0 # Initialize a queue to store # pair of node and level q = [] # Push the root into the # queue with level 1 q.append([root, 1]) # Iterate all levels # of tree are traversed while (len(q) != 0): # Store the node at the # front of the queue currNode = q[0] # Pop the front node q.pop(0) # Store the current level currLevel = currNode[1] # Store the current node value currVal = currNode[0].val # If current node # level is odd if (currLevel % 2 != 0): # Add to odd sum oddSum += currVal else: # Add to even sum evenSum += currVal # Push all the children of current node # with increasing current level by 1 for child in currNode[0].children: q.append([child, currLevel + 1]) # Return the difference return (oddSum - evenSum) # Driver code if __name__=="__main__": # Create the N-ary Tree root = newNode(4) root.children.append(newNode(2)) root.children.append(newNode(3)) root.children.append(newNode(-5)) root.children[0].children.append(newNode(-1)) root.children[0].children.append(newNode(3)) root.children[2].children.append(newNode(-2)) root.children[2].children.append(newNode(6)) print(evenOddLevelDifference(root)) # This code is contributed by rutvik_56
C#
// C# program to implement // the above approach using System; using System.Collections; using System.Collections.Generic; class GFG{ // Structure of a node // of an n-ary tree class Node { public int val; public ArrayList children; public Node(int val) { this.val = val; this.children = new ArrayList(); } }; class Pair { public Node first; public int second; public Pair(Node node, int val) { this.first = node; this.second = val; } } // Function to find the difference // between of sums node values of // odd and even levels in an N-ary tree static int evenOddLevelDifference(Node root) { // Store the sums of nodes at // even and odd levels int evenSum = 0, oddSum = 0; // Initialize a queue to store // pair of node and level Queue q = new Queue(); // Push the root into the // queue with level 1 q.Enqueue(new Pair(root, 1)); // Iterate all levels // of tree are traversed while (q.Count != 0) { // Store the node at the // front of the queue Pair currNode = (Pair)q.Dequeue(); // Store the current level int currLevel = currNode.second; // Store the current node value int currVal = currNode.first.val; // If current node // level is odd if (currLevel % 2 == 1) // Add to odd sum oddSum += currVal; else // Add to even sum evenSum += currVal; // Push all the children of current node // with increasing current level by 1 foreach(Node child in currNode.first.children) { q.Enqueue(new Pair(child, currLevel + 1)); } } // Return the difference return(oddSum - evenSum); } // Driver Code public static void Main(string[] args) { // Create the N-ary Tree Node root = new Node(4); root.children.Add(new Node(2)); root.children.Add(new Node(3)); root.children.Add(new Node(-5)); ((Node)root.children[0]).children.Add(new Node(-1)); ((Node)root.children[0]).children.Add(new Node(3)); ((Node)root.children[2]).children.Add(new Node(-2)); ((Node)root.children[2]).children.Add(new Node(6)); Console.Write(evenOddLevelDifference(root)); } } // This code is contributed by pratham76
Javascript
<script> // JavaScript implementation of the above approach // Structure of a node of an n-ary tree // Structure of a Tree Node class Node { constructor(val) { this.children = []; this.val = val; } } // Function to find the difference // between of sums node values of // odd and even levels in an N-ary tree function evenOddLevelDifference(root) { // Store the sums of nodes at // even and odd levels let evenSum = 0, oddSum = 0; // Initialize a queue to store // pair of node and level let q = []; // Push the root into the // queue with level 1 q.push([root, 1]); // Iterate all levels // of tree are traversed while (q.length != 0) { // Store the node at the // front of the queue let currNode = q[0]; q.shift(); // Store the current level let currLevel = currNode[1]; // Store the current node value let currVal = currNode[0].val; // If current node // level is odd if (currLevel % 2 == 1) // Add to odd sum oddSum += currVal; else // Add to even sum evenSum += currVal; // Push all the children of current node // with increasing current level by 1 for(let child = 0; child < (currNode[0].children).length; child++) { q.push([currNode[0].children[child], currLevel + 1]); } } // Return the difference return(oddSum - evenSum); } // Create the N-ary Tree let root = new Node(4); root.children.push(new Node(2)); root.children.push(new Node(3)); root.children.push(new Node(-5)); (root.children[0]).children.push(new Node(-1)); (root.children[0]).children.push(new Node(3)); (root.children[2]).children.push(new Node(-2)); (root.children[2]).children.push(new Node(6)); document.write(evenOddLevelDifference(root)); </script>
10
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por muskan_garg y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA