Dado un árbol binario que tiene N Nodes, la tarea es encontrar el nivel que tiene el número máximo de bits establecidos.
Nota: Si dos niveles tienen el mismo número de setbits, imprima el que tenga menos Nodes. Si los Nodes son iguales, imprima el primer nivel de arriba a abajo
Ejemplos:
Entrada:
2
/ \
5 3
/ \
6 1
Salida: 2
Explicación: El nivel 1 tiene solo un setbit => 2 (010).
El nivel 2 tiene 4 setbits. => 5 (101) + 3 (011).
El nivel 3 tiene 3 setbits. => 6 (110) +1 (001).Entrada:
2
/ \
5 3
/ \ \
6 1 8
Salida: 2
Enfoque: el problema se puede resolver usando el recorrido de orden de niveles en sí mismo. Encuentre el número de setbits en cada nivel y el nivel que tiene el número máximo de setbits siguiendo la condición dada en el problema. Siga los pasos que se mencionan a continuación:
- Utilice el recorrido de orden de nivel y para cada nivel:
- Encuentre el número total de setbits en cada nivel.
- Actualiza los setbits máximos en un nivel y el nivel que tiene el número máximo de setbits.
- Devuelve el nivel con los setbits máximos.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code to implement the above approach
#include <bits/stdc++.h>
using namespace std;
// Structure of a binary tree node
struct Node {
int data;
struct Node *left, *right;
};
// Function to count no of set bit
int countSetBit(int x)
{
int c = 0;
while (x) {
int l = x % 10;
if (x & 1)
c++;
x /= 2;
}
return c;
}
// Function to convert tree element
// by count of set bit they have
void convert(Node* root)
{
if (!root)
return;
root->data = countSetBit(root->data);
convert(root->left);
convert(root->right);
}
// Function to get level with max set bit
int printLevel(Node* root)
{
// Base Case
if (root == NULL)
return 0;
// Replace tree elements by
// count of set bits they contain
convert(root);
// Create an empty queue
queue<Node*> q;
int currLevel = 0, ma = INT_MIN;
int prev = 0, ans = 0;
// Enqueue Root and initialize height
q.push(root);
// Loop to implement level order traversal
while (q.empty() == false) {
// Print front of queue and
// remove it from queue
int size = q.size();
currLevel++;
int totalSet = 0, nodeCount = 0;
while (size--) {
Node* node = q.front();
// Add all the set bit
// in the current level
totalSet += node->data;
q.pop();
// Enqueue left child
if (node->left != NULL)
q.push(node->left);
// Enqueue right child
if (node->right != NULL)
q.push(node->right);
// Count current level node
nodeCount++;
}
// Update the ans when needed
if (ma < totalSet) {
ma = totalSet;
ans = currLevel;
}
// If two level have same set bit
// one with less node become ans
else if (ma == totalSet && prev > nodeCount) {
ma = totalSet;
ans = currLevel;
prev = nodeCount;
}
// Assign prev =
// current level node count
// We can use it for further levels
// When 2 level have
// same set bit count
// print level with less node
prev = nodeCount;
}
return ans;
}
// Utility function to create new tree node
Node* newNode(int data)
{
Node* temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
// Driver program
int main()
{
// Binary tree as shown in example
Node* root = newNode(2);
root->left = newNode(5);
root->right = newNode(3);
root->left->left = newNode(6);
root->left->right = newNode(1);
root->right->right = newNode(8);
// Function call
cout << printLevel(root) << endl;
return 0;
}
Java
// Java code to implement the above approach
import java.util.*;
class GFG{
// Structure of a binary tree node
static class Node {
int data;
Node left, right;
};
// Function to count no of set bit
static int countSetBit(int x)
{
int c = 0;
while (x!=0) {
int l = x % 10;
if (x%2==1)
c++;
x /= 2;
}
return c;
}
// Function to convert tree element
// by count of set bit they have
static void convert(Node root)
{
if (root==null)
return;
root.data = countSetBit(root.data);
convert(root.left);
convert(root.right);
}
// Function to get level with max set bit
static int printLevel(Node root)
{
// Base Case
if (root == null)
return 0;
// Replace tree elements by
// count of set bits they contain
convert(root);
// Create an empty queue
Queue<Node> q = new LinkedList<>();
int currLevel = 0, ma = Integer.MIN_VALUE;
int prev = 0, ans = 0;
// Enqueue Root and initialize height
q.add(root);
// Loop to implement level order traversal
while (q.isEmpty() == false) {
// Print front of queue and
// remove it from queue
int size = q.size();
currLevel++;
int totalSet = 0, nodeCount = 0;
while (size-- >0) {
Node node = q.peek();
// Add all the set bit
// in the current level
totalSet += node.data;
q.remove();
// Enqueue left child
if (node.left != null)
q.add(node.left);
// Enqueue right child
if (node.right != null)
q.add(node.right);
// Count current level node
nodeCount++;
}
// Update the ans when needed
if (ma < totalSet) {
ma = totalSet;
ans = currLevel;
}
// If two level have same set bit
// one with less node become ans
else if (ma == totalSet && prev > nodeCount) {
ma = totalSet;
ans = currLevel;
prev = nodeCount;
}
// Assign prev =
// current level node count
// We can use it for further levels
// When 2 level have
// same set bit count
// print level with less node
prev = nodeCount;
}
return ans;
}
// Utility function to create new tree node
static Node newNode(int data)
{
Node temp = new Node();
temp.data = data;
temp.left = temp.right = null;
return temp;
}
// Driver program
public static void main(String[] args)
{
// Binary tree as shown in example
Node root = newNode(2);
root.left = newNode(5);
root.right = newNode(3);
root.left.left = newNode(6);
root.left.right = newNode(1);
root.right.right = newNode(8);
// Function call
System.out.print(printLevel(root) +"\n");
}
}
// This code is contributed by shikhasingrajput
Python3
# Python code for the above approach # Structure of a binary Tree node import sys class Node: def __init__(self,d): self.data = d self.left = None self.right = None # Function to count no of set bit def countSetBit(x): c = 0 while (x): l = x % 10 if (x & 1): c += 1 x = (x // 2) return c # Function to convert tree element # by count of set bit they have def convert(root): if (root == None): return root.data = countSetBit(root.data) convert(root.left) convert(root.right) # Function to get level with max set bit def printLevel(root): # Base Case if (root == None): return 0 # Replace tree elements by # count of set bits they contain convert(root) # Create an empty queue q = [] currLevel,ma = 0, -sys.maxsize - 1 prev,ans = 0,0 # Enqueue Root and initialize height q.append(root) # Loop to implement level order traversal while (len(q) != 0): # Print front of queue and # remove it from queue size = len(q) currLevel += 1 totalSet,nodeCount = 0,0 while (size): node = q[0] q = q[1:] # Add all the set bit # in the current level totalSet += node.data # Enqueue left child if (node.left != None): q.append(node.left) # Enqueue right child if (node.right != None): q.append(node.right) # Count current level node nodeCount += 1 size -= 1 # Update the ans when needed if (ma < totalSet): ma = totalSet ans = currLevel # If two level have same set bit # one with less node become ans elif (ma == totalSet and prev > nodeCount): ma = totalSet ans = currLevel prev = nodeCount # Assign prev = # current level node count # We can use it for further levels # When 2 level have # same set bit count # print level with less node prev = nodeCount return ans # Driver program # Binary tree as shown in example root = Node(2) root.left = Node(5) root.right = Node(3) root.left.left = Node(6) root.left.right = Node(1) root.right.right = Node(8) # Function call print(printLevel(root)) # This code is contributed by shinjanpatra
C#
// C# code to implement the above approach
using System;
using System.Collections.Generic;
public class GFG{
// Structure of a binary tree node
class Node {
public int data;
public Node left, right;
};
// Function to count no of set bit
static int countSetBit(int x)
{
int c = 0;
while (x!=0) {
int l = x % 10;
if (x%2==1)
c++;
x /= 2;
}
return c;
}
// Function to convert tree element
// by count of set bit they have
static void convert(Node root)
{
if (root==null)
return;
root.data = countSetBit(root.data);
convert(root.left);
convert(root.right);
}
// Function to get level with max set bit
static int printLevel(Node root)
{
// Base Case
if (root == null)
return 0;
// Replace tree elements by
// count of set bits they contain
convert(root);
// Create an empty queue
Queue<Node> q = new Queue<Node>();
int currLevel = 0, ma = int.MinValue;
int prev = 0, ans = 0;
// Enqueue Root and initialize height
q.Enqueue(root);
// Loop to implement level order traversal
while (q.Count!=0 ) {
// Print front of queue and
// remove it from queue
int size = q.Count;
currLevel++;
int totalSet = 0, nodeCount = 0;
while (size-- >0) {
Node node = q.Peek();
// Add all the set bit
// in the current level
totalSet += node.data;
q.Dequeue();
// Enqueue left child
if (node.left != null)
q.Enqueue(node.left);
// Enqueue right child
if (node.right != null)
q.Enqueue(node.right);
// Count current level node
nodeCount++;
}
// Update the ans when needed
if (ma < totalSet) {
ma = totalSet;
ans = currLevel;
}
// If two level have same set bit
// one with less node become ans
else if (ma == totalSet && prev > nodeCount) {
ma = totalSet;
ans = currLevel;
prev = nodeCount;
}
// Assign prev =
// current level node count
// We can use it for further levels
// When 2 level have
// same set bit count
// print level with less node
prev = nodeCount;
}
return ans;
}
// Utility function to create new tree node
static Node newNode(int data)
{
Node temp = new Node();
temp.data = data;
temp.left = temp.right = null;
return temp;
}
// Driver program
public static void Main(String[] args)
{
// Binary tree as shown in example
Node root = newNode(2);
root.left = newNode(5);
root.right = newNode(3);
root.left.left = newNode(6);
root.left.right = newNode(1);
root.right.right = newNode(8);
// Function call
Console.Write(printLevel(root) +"\n");
}
}
// This code contributed by shikhasingrajput
Javascript
<script>
// JavaScript code for the above approach
// Structure of a binary Tree node
class Node {
constructor(d) {
this.data = d;
this.left = null;
this.right = null;
}
};
// Function to count no of set bit
function countSetBit(x) {
let c = 0;
while (x) {
let l = x % 10;
if (x & 1)
c++;
x = Math.floor(x / 2);
}
return c;
}
// Function to convert tree element
// by count of set bit they have
function convert(root) {
if (root == null)
return;
root.data = countSetBit(root.data);
convert(root.left);
convert(root.right);
}
// Function to get level with max set bit
function printLevel(root) {
// Base Case
if (root == null)
return 0;
// Replace tree elements by
// count of set bits they contain
convert(root);
// Create an empty queue
let q = [];
let currLevel = 0, ma = Number.MIN_VALUE;
let prev = 0, ans = 0;
// Enqueue Root and initialize height
q.push(root);
// Loop to implement level order traversal
while (q.length != 0) {
// Print front of queue and
// remove it from queue
let size = q.length;
currLevel++;
let totalSet = 0, nodeCount = 0;
while (size--) {
let node = q.shift();
// Add all the set bit
// in the current level
totalSet += node.data;
q.pop();
// Enqueue left child
if (node.left != null)
q.push(node.left);
// Enqueue right child
if (node.right != null)
q.push(node.right);
// Count current level node
nodeCount++;
}
// Update the ans when needed
if (ma < totalSet) {
ma = totalSet;
ans = currLevel;
}
// If two level have same set bit
// one with less node become ans
else if (ma == totalSet && prev > nodeCount) {
ma = totalSet;
ans = currLevel;
prev = nodeCount;
}
// Assign prev =
// current level node count
// We can use it for further levels
// When 2 level have
// same set bit count
// print level with less node
prev = nodeCount;
}
return ans;
}
// Driver program
// Binary tree as shown in example
let root = new Node(2);
root.left = new Node(5);
root.right = new Node(3);
root.left.left = new Node(6);
root.left.right = new Node(1);
root.right.right = new Node(8);
// Function call
document.write(printLevel(root) + '<br>');
// This code is contributed by Potta Lokesh
</script>
Producción
2
Complejidad de Tiempo: (N * D) donde D no es de bit un elemento tiene
Espacio Auxiliar: O(N)