Diferencia entre la suma de hojas de nivel impar y nivel par en un árbol binario dado

Dado un árbol binario , la tarea es encontrar la diferencia de la suma de los Nodes hoja en el nivel impar y en el nivel par del árbol dado .

Ejemplos:

Aporte:

Salida: -12
Explicación: Las siguientes son las operaciones realizadas para obtener el resultado.
odd_level_sum = 0, even_level_sum = 0
Nivel 1: sin Node hoja, por lo que odd_level_sum = 0
Nivel 2: sin Node hoja, por lo que even_level_sum = 0
Nivel 3: un Node hoja: 6, por lo que odd_level_sum = 0 + 6 = 6 
Nivel 4: tres Nodes hoja: 9, 10, 11, entonces even_level_sum = 0 + 9 + 10 + 11 = 30
Nivel 5: Un Node hoja: 12, entonces odd_level_sum = 6 + 12 = 18
Por lo tanto, result = odd_level_sum – even_level_sum = 18 – 30 = -12

Aporte:

Salida: -12

Enfoque: El problema dado se puede resolver utilizando el recorrido de orden de nivel . Siga los pasos a continuación para resolver el problema dado.

• Cree una cola q para almacenar el Node. Además, cree dos variables odd_level_sum y even_level_sum para almacenar la suma de los Nodes hoja en los niveles pares e impares del árbol, respectivamente. El otro nivel variable realiza un seguimiento del nivel en el recorrido.
• Realice el recorrido de orden de nivel desde el Node raíz y almacene cada Node en la cola, y también verifique el Node actual para el Node hoja. Si es un Node hoja, agregue su valor en odd_level_sum o even_level_sum al verificar el nivel.
• Después de completar los pasos anteriores, imprima la diferencia entre odd_level_sum y even_level_sum .

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

// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
 
// A tree node structure
struct Node {
    int data;
    Node *left, *right;
};
 
// Utility function to create
// a new Binary Tree node
Node* newNode(int data)
{
    Node* temp = new Node;
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}
 
// Function to print the difference
void printDifference(Node* root)
{
    if (root == NULL) {
        cout << "No nodes present\n";
        return;
    }
 
    int odd_level_sum = 0,
        even_level_sum = 0,
        level = 1;
 
    // queue to hold tree node with level
    queue<struct Node*> q;
 
    // Root node is at level 1 so level=1
    q.push(root);
 
    // Do level Order Traversal of tree
    while (!q.empty()) {
        int n = q.size();
        while (n--) {
            Node* temp = q.front();
            q.pop();
            if (temp->left == NULL
                && temp->right == NULL) {
                if (level & 1) {
                    odd_level_sum += temp->data;
                }
                else {
                    even_level_sum += temp->data;
                }
                continue;
            }
            if (temp->left) {
                q.push(temp->left);
            }
            if (temp->right) {
                q.push(temp->right);
            }
        }
        level++;
    }
    cout << odd_level_sum - even_level_sum;
}
 
// Driver Code
int main()
{
    Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->left = newNode(6);
    root->right->right = newNode(7);
    root->left->left->right = newNode(8);
    root->left->right->right = newNode(9);
    root->right->right->left = newNode(10);
    root->right->right->right = newNode(11);
    root->left->left->right->right = newNode(12);
 
    printDifference(root);
 
    return 0;
}

// Java program for above approach
import java.util.LinkedList;
import java.util.Queue;
 
class GFG {
 
  // A tree node structure
  static class Node {
    int data;
    Node left;
    Node right;
 
    public Node(int data) {
      this.data = data;
      this.left = null;
      this.right = null;
    }
  };
 
  // Utility function to create
  // a new Binary Tree node
  static Node Node(int data) {
    Node temp = new Node(0);
    temp.data = data;
    temp.left = temp.right = null;
    return temp;
  }
 
  // Function to print the difference
  static void printDifference(Node root) {
    if (root == null) {
      System.out.println("No nodes present");
      return;
    }
 
    int odd_level_sum = 0,
    even_level_sum = 0,
    level = 1;
 
    // queue to hold tree node with level
    Queue<Node> q = new LinkedList<Node>();
 
    // Root node is at level 1 so level=1
    q.add(root);
 
    // Do level Order Traversal of tree
    while (!q.isEmpty()) {
      int n = q.size();
      while (n-- > 0) {
        Node temp = q.peek();
        q.remove();
        if (temp.left == null
            && temp.right == null) {
          if ((level & 1) > 0) {
            odd_level_sum += temp.data;
          } else {
            even_level_sum += temp.data;
          }
          continue;
        }
        if (temp.left != null) {
          q.add(temp.left);
        }
        if (temp.right != null) {
          q.add(temp.right);
        }
      }
      level++;
    }
    System.out.println(odd_level_sum - even_level_sum);
  }
 
  // Driver Code
  public static void main(String args[]) {
    Node root = new Node(1);
    root.left = new Node(2);
    root.right = new Node(3);
    root.left.left = new Node(4);
    root.left.right = new Node(5);
    root.right.left = new Node(6);
    root.right.right = new Node(7);
    root.left.left.right = new Node(8);
    root.left.right.right = new Node(9);
    root.right.right.left = new Node(10);
    root.right.right.right = new Node(11);
    root.left.left.right.right = new Node(12);
 
    printDifference(root);
 
  }
}
 
// This code is contributed by saurabh_jaiswal.

// C# program for the above approach
 
using System;
using System.Collections.Generic;
 
public class GFG {
 
    // A tree node strucute
    class Node {
        public int data;
        public Node left, right;
        public Node(int d)
        {
            data = d;
            left = null;
            right = null;
        }
    }
 
    // Utility function to create a new Binary Tree node
    static Node node(int data)
    {
        Node temp = new Node(0);
        temp.data = data;
        temp.left = temp.right = null;
        return temp;
    }
 
    // Function to print the difference
    static void printDifference(Node root)
    {
        if (root == null) {
            Console.WriteLine("No nodes presesnt");
            return;
        }
        int odd_level_sum = 0;
        int even_level_sum = 0;
        int level = 1;
 
        // Queue to hold tree node with level
        Queue<Node> q = new Queue<Node>();
 
        // Root node is at level 1, so level=1.
        q.Enqueue(root);
 
        // Do level order traversal of a tree.
        while (q.Count != 0) {
            int n = q.Count;
            while (n-- > 0) {
                Node temp = q.Dequeue();
                if (temp.left == null
                    && temp.right == null) {
                    if ((level & 1) > 0) {
                        odd_level_sum += temp.data;
                    }
                    else {
                        even_level_sum += temp.data;
                    }
                    continue;
                }
                if (temp.left != null) {
                    q.Enqueue(temp.left);
                }
                if (temp.right != null) {
                    q.Enqueue(temp.right);
                }
            }
            level++;
        }
        Console.WriteLine(odd_level_sum - even_level_sum);
    }
 
    static public void Main()
    {
 
        // Code
        Node root = node(1);
        root.left = node(2);
        root.right = node(3);
        root.left.left = node(4);
        root.left.right = node(5);
        root.right.left = node(6);
        root.right.right = node(7);
        root.left.left.right = node(8);
        root.left.right.right = node(9);
        root.right.right.left = node(10);
        root.right.right.right = node(11);
        root.left.left.right.right = node(12);
 
        printDifference(root);
    }
}
 
// This code is contributed by lokesh(lokeshmvs21).

-12

Complejidad temporal: O(N) 
Complejidad espacial: O(N)