Suma de equivalentes decimales de valores de Nodes binarios en cada nivel de un árbol binario

Dado un árbol binario que consta de Nodes con valores 0 y 1 únicamente, la tarea es encontrar la suma total de los equivalentes decimales de los números binarios formados al conectar Nodes en el mismo nivel de izquierda a derecha , en cada nivel.

Ejemplos:

Entrada: A continuación se muestra el árbol dado:
                  0
                / \
              1 0
             / \ / \
           0 1 1 1
Salida: 9
Explicación: 
El número binario formado en el nivel 1 es «0» y su equivalente decimal es 0.
El número binario formado en el nivel 2 es “10” y su equivalente decimal es 2.
El número binario formado en el nivel 3 es “0111” y su equivalente decimal es 7.
Por tanto, suma total = 0 + 2 + 7 = 9.

Entrada: A continuación se muestra el árbol dado:
                 0
               /
             1
            / \
          1 0
Salida: 3

Enfoque: La idea es realizar un recorrido de orden de nivel utilizando una cola y encontrar la suma de los números formados en cada nivel. Siga los pasos a continuación para resolver el problema:

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

C++

// CPP program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Structure of a Tree Node
class TreeNode {
 public:
  int val;
  TreeNode *left, *right;
 
  TreeNode(int key) {
    val = key;
    left = right = NULL;
  }
};
 
// Function to convert binary number
// to its equivalent decimal value
int convertBinaryToDecimal(vector<int> arr) {
  int ans = 0;
  for (int i : arr) ans = (ans << 1) | i;
 
  return ans;
}
 
// Function to calculate sum of
// decimal equivalent of binary numbers
// of node values present at each level
void decimalEquilvalentAtEachLevel(TreeNode *root) {
  int ans = 0;
 
  queue<TreeNode *> que;
 
  // Push root node into queue
  que.push(root);
 
  while (true) {
    int length = que.size();
    if (length == 0) break;
    vector<int> eachLvl;
 
    // Connect nodes at the same
    // level to form a binary number
    while (length > 0) {
      TreeNode *temp = que.front();
      que.pop();
 
      // Append the value of the
      // current node to eachLvl
      eachLvl.push_back(temp->val);
 
      // Insert the Left child to
      // queue, if its not NULL
      if (temp->left != NULL) que.push(temp->left);
 
      // Insert the Right child to
      // queue, if its not NULL
      if (temp->right != NULL) que.push(temp->right);
 
      // Decrement length by one
      length -= 1;
 
      // Stores the front
      // element of the queue
    }
 
    // Add decimal equivalent of the
    // binary number formed on the
    // current level to ans
    ans += convertBinaryToDecimal(eachLvl);
  }
 
  // Finally print ans
  cout << ans << endl;
}
 
// Driver Code
int main()
{
   
  // Given Tree
  TreeNode *root = new TreeNode(0);
  root->left = new TreeNode(1);
  root->right = new TreeNode(0);
  root->left->left = new TreeNode(0);
  root->left->right = new TreeNode(1);
  root->right->left = new TreeNode(1);
  root->right->right = new TreeNode(1);
 
  // Function Call
  decimalEquilvalentAtEachLevel(root);
 
  return 0;
}
 
// This code is contributed by sanjeev2552

Java

// Java program for the above approach
 
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
 
class GFG {
 
    // Structure of a Tree Node
    static class TreeNode {
        int val;
        TreeNode left, right;
 
        public TreeNode(int key) {
            val = key;
            left = right = null;
        }
    }
 
    // Function to convert binary number
    // to its equivalent decimal value
    static int convertBinaryToDecimal(ArrayList<Integer> arr) {
        int ans = 0;
        for (int i : arr)
            ans = (ans << 1) | i;
 
        return ans;
 
    }
 
    // Function to calculate sum of
    // decimal equivalent of binary numbers
    // of node values present at each level
    static void decimalEquilvalentAtEachLevel(TreeNode root) {
 
        int ans = 0;
 
        Queue<TreeNode> que = new LinkedList<>();
 
        // Push root node into queue
        que.add(root);
 
        while (true) {
            int length = que.size();
            if (length == 0)
                break;
            ArrayList<Integer> eachLvl = new ArrayList<>();
 
            // Connect nodes at the same
            // level to form a binary number
            while (length > 0) {
 
                TreeNode temp = que.poll();
 
                // Append the value of the
                // current node to eachLvl
                eachLvl.add(temp.val);
 
                // Insert the Left child to
                // queue, if its not NULL
                if (temp.left != null)
                    que.add(temp.left);
 
                // Insert the Right child to
                // queue, if its not NULL
                if (temp.right != null)
                    que.add(temp.right);
 
                // Decrement length by one
                length -= 1;
 
                // Stores the front
                // element of the queue
            }
 
            // Add decimal equivalent of the
            // binary number formed on the
            // current level to ans
            ans += convertBinaryToDecimal(eachLvl);
        }
 
        // Finally print ans
        System.out.println(ans);
    }
 
    // Driver Code
    public static void main(String[] args) {
 
        // Given Tree
        TreeNode root = new TreeNode(0);
        root.left = new TreeNode(1);
        root.right = new TreeNode(0);
        root.left.left = new TreeNode(0);
        root.left.right = new TreeNode(1);
        root.right.left = new TreeNode(1);
        root.right.right = new TreeNode(1);
 
        // Function Call
        decimalEquilvalentAtEachLevel(root);
    }
 
    // This code is contributed by sanjeev2552
}

Python3

# Python3 program for the above approach
 
# Structure of a Tree Node
class TreeNode:
    def __init__(self, val = 0,
                 left = None, right = None):
        self.val = val
        self.left = left
        self.right = right
 
# Function to convert binary number
# to its equivalent decimal value
def convertBinaryToDecimal(arr):
 
    ans = 0
 
    for i in arr:
        ans = (ans << 1) | i
 
    return ans
 
# Function to calculate sum of
# decimal equivalent of binary numbers
# of node values present at each level
def decimalEquilvalentAtEachLevel(root):
 
    ans = 0
     
    # Push root node into queue
    que = [root]
 
    while True:
        length = len(que)
        if not length:
            break
        eachLvl = []
         
        # Connect nodes at the same
        # level to form a binary number
        while length:
           
            # Stores the front
            # element of the queue
            temp = que.pop(0)
 
            # Append the value of the
            # current node to eachLvl
            eachLvl.append(temp.val)
 
            # Insert the Left child to
            # queue, if its not NULL
            if temp.left:
                que.append(temp.left)
 
            # Insert the Right child to
            # queue, if its not NULL
            if temp.right:
                que.append(temp.right)
                 
            # Decrement length by one
            length -= 1
             
        # Add decimal equivalent of the
        # binary number formed on the
        # current level to ans
        ans += convertBinaryToDecimal(eachLvl)
 
    # Finally print ans
    print(ans)
 
 
# Driver Code
 
# Given Tree
root = TreeNode(0)
root.left = TreeNode(1)
root.right = TreeNode(0)
root.left.left = TreeNode(0)
root.left.right = TreeNode(1)
root.right.left = TreeNode(1)
root.right.right = TreeNode(1)
 
# Function Call
decimalEquilvalentAtEachLevel(root)

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
    
   // Structure of a Tree Node
class TreeNode{
  public int val;
  public TreeNode left,right;
};
 
static TreeNode newNode(int key){
  TreeNode temp = new TreeNode();
  temp.val = key;
  temp.left = temp.right = null;
  return temp;
}
// Function to convert binary number
// to its equivalent decimal value
static int convertBinaryToDecimal(List<int> arr)
{  
   int ans = 0;
    foreach(int i in arr)
        ans = (ans << 1) | i;
 
    return ans;
 
}
 
// Function to calculate sum of
// decimal equivalent of binary numbers
// of node values present at each level
static void decimalEquilvalentAtEachLevel(TreeNode root){
 
    int ans = 0;
     
    Queue<TreeNode> que = new Queue<TreeNode>();
   
    // Push root node into queue
    que.Enqueue(root);
 
    while(true){
       int length = que.Count;
        if (length == 0)
            break;
        List<int> eachLvl = new List<int>();
         
        // Connect nodes at the same
        // level to form a binary number
        while(length > 0){
 
          TreeNode temp = que.Peek();
          que.Dequeue();
 
            // Append the value of the
            // current node to eachLvl
            eachLvl.Add(temp.val);
 
            // Insert the Left child to
            // queue, if its not NULL
            if (temp.left != null)
                que.Enqueue(temp.left);
 
            // Insert the Right child to
            // queue, if its not NULL
            if (temp.right!=null)
                que.Enqueue(temp.right);
                 
            // Decrement length by one
            length -= 1;
           
            // Stores the front
            // element of the queue
        }
             
        // Add decimal equivalent of the
        // binary number formed on the
        // current level to ans
        ans += convertBinaryToDecimal(eachLvl);
    }
 
    // Finally print ans
    Console.WriteLine(ans);
}
 
// Driver Code
public static void Main()
{
   
    // Given Tree
TreeNode root = newNode(0);
root.left = newNode(1);
root.right = newNode(0);
root.left.left = newNode(0);
root.left.right = newNode(1);
root.right.left = newNode(1);
root.right.right = newNode(1);
 
// Function Call
decimalEquilvalentAtEachLevel(root);
}
}
 
// This code is contributed by SURENDRA_GANGWAR.

Javascript

<script>
 
// JavaScript program for the above approach
 
   // Structure of a Tree Node
class TreeNode{
 
  constructor()
  {
    this.val = 0;
    this.left = null;
    this.right = null;
  }
};
 
function newNode( key){
  var temp = new TreeNode();
  temp.val = key;
  temp.left = temp.right = null;
  return temp;
}
// Function to convert binary number
// to its equivalent decimal value
function convertBinaryToDecimal(arr)
{  
   var ans = 0;
    for(var i of arr)
        ans = (ans << 1) | i;
 
    return ans;
 
}
 
// Function to calculate sum of
// decimal equivalent of binary numbers
// of node values present at each level
function decimalEquilvalentAtEachLevel( root){
 
    var ans = 0;
     
    var que = [];
   
    // Push root node into queue
    que.push(root);
 
    while(true){
       var length = que.length;
        if (length == 0)
            break;
        var eachLvl = [];
         
        // Connect nodes at the same
        // level to form a binary number
        while(length > 0){
 
          var temp = que[0];
          que.shift();
 
            // Append the value of the
            // current node to eachLvl
            eachLvl.push(temp.val);
 
            // Insert the Left child to
            // queue, if its not NULL
            if (temp.left != null)
                que.push(temp.left);
 
            // Insert the Right child to
            // queue, if its not NULL
            if (temp.right!=null)
                que.push(temp.right);
                 
            // Decrement length by one
            length -= 1;
           
            // Stores the front
            // element of the queue
        }
             
        // Add decimal equivalent of the
        // binary number formed on the
        // current level to ans
        ans += convertBinaryToDecimal(eachLvl);
    }
 
    // Finally print ans
    document.write(ans);
}
 
// Driver Code
 
// Given Tree
var root = newNode(0);
root.left = newNode(1);
root.right = newNode(0);
root.left.left = newNode(0);
root.left.right = newNode(1);
root.right.left = newNode(1);
root.right.right = newNode(1);
 
// Function Call
decimalEquilvalentAtEachLevel(root);
 
</script>
Producción: 

9

 

Complejidad temporal: O(N)
Espacio auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por rohitsingh07052 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 *