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:
- Inicialice una cola , digamos Q , para realizar el recorrido de orden de nivel y una variable, digamos ans , para almacenar la suma del número formado.
- Empuje el Node raíz a la cola Q.
- Iterar hasta que la cola se vacíe y realizar los siguientes pasos:
- Iterar sobre el rango [1, Q.size()] y conectar todos los Nodes en ese nivel y empujar a los hijos de los respectivos Nodes en la cola Q .
- Encuentre el equivalente decimal del número binario formado y agregue este número a ans .
- Después de completar los pasos anteriores, imprima el valor de ans como la suma resultante.
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