Diferencia entre sumas de Nodes de nivel impar y de nivel par en un árbol N-ario

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 7  

Salida: -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>
Producción: 

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *