Dado un árbol binario que consta de N Nodes, la tarea es contar el número de niveles en un árbol binario de modo que los bits establecidos de todos los valores de Node en el mismo nivel estén en diferentes posiciones.
Ejemplos:
Aporte:
5 / \ 6 9 / \ \ 1 4 7Salida: 2
Explicación:
El nivel 1 tiene solo 5 (= (101) 2 ).
El nivel 2 tiene 6 (= (0110) 2 ) y 9 (= (1001) 2 ). Todos los bits establecidos están en posiciones únicas.
El nivel 3 tiene 1 (0001) 2 , 4 (0100) 2 y 7(0111) 2 . Por lo tanto, se establece el bit 0 de los valores de Node 5 y 7.Aporte:
1 / \ 2 3 / \ \ 5 4 7Salida: 1
Enfoque ingenuo: el enfoque más simple para resolver este problema es atravesar el árbol binario utilizando el orden transversal de nivel y en cada nivel del árbol almacenar los bits establecidos de todos los Nodes utilizando Map. Recorra el mapa y verifique si la frecuencia de los bits establecidos en la misma posición es menor o igual a 1 o no. Si se encuentra que es cierto, entonces incremente el conteo. Finalmente, imprima el conteo obtenido.
Complejidad temporal: O(N)
Espacio auxiliar: O(32)
Enfoque eficiente: el enfoque anterior se puede optimizar en función de las siguientes observaciones:
Si todos los bits establecidos de dos números A y B están en posiciones diferentes
A XOR B = A OR B
Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos prefiX_XOR , para almacenar el prefijo XOR de todos los Nodes en cada nivel.
- Inicialice una variable, digamos prefiX_OR , para almacenar el prefijo OR de todos los Nodes en cada nivel.
- Recorra el árbol binario utilizando el recorrido de orden de nivel . En cada nivel i , compruebe si prefix_XOR ^ nodes es igual a (prefix_OR | nodes) o no. Si se encuentra que es cierto para todos los Nodes en el nivel actual, entonces incremente el conteo.
- Finalmente, imprima el conteo obtenido.
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Structure of a node in
// the binary tree
struct TreeNode
{
int val = 0;
TreeNode *left,*right;
TreeNode(int x)
{
val = x;
left = NULL;
right = NULL;
}
};
// Function to find total unique levels
void uniqueLevels(TreeNode *root)
{
// Stores count of levels, where the set
// bits of all the nodes are at
// different positions
int uniqueLevels = 0;
// Store nodes at each level of
// the tree using BFS
queue<TreeNode*> que;
que.push(root);
// Performing level order traversal
while (que.size() > 0)
{
// Stores count of nodes at
// current level
int length = que.size();
// Stores prefix XOR of all
// the nodes at current level
int prefix_XOR = 0;
// Stores prefix OR of all
// the nodes at current level
int prefix_OR = 0;
// Check if set bit of all the nodes
// at current level is at different
// positions or not
bool flag = true;
// Traverse nodes at current level
for(int i = 0; i < length; i++){
// Stores front element
// of the que
TreeNode *temp = que.front();
que.pop();
// Update prefix_OR
prefix_OR |= temp->val;
// Update prefix_XOR
prefix_XOR ^= temp->val;
if (prefix_XOR != prefix_OR)
flag = false;
// If left subtree not NULL
if (temp->left)
que.push(temp->left);
// If right subtree not NULL
if (temp->right)
que.push(temp->right);
// Update length
}
//If bitwise AND is zero
if (flag)
uniqueLevels += 1;
}
cout << uniqueLevels;
}
// Driver Code
int main()
{
TreeNode *root = new TreeNode(5);
root->left = new TreeNode(6);
root->right = new TreeNode(9);
root->left->left = new TreeNode(1);
root->left->right = new TreeNode(4);
root->right->right = new TreeNode(7);
// Function Call
uniqueLevels(root);
return 0;
}
// This code is contributed by mohit kumar 29.
Java
// Java program for the above approach
import java.util.*;
class GFG
{
// Structure of a node in
// the binary tree
static class TreeNode
{
int val = 0;
TreeNode left, right;
TreeNode(int x)
{
val = x;
left = null;
right = null;
}
};
// Function to find total unique levels
static void uniqueLevels(TreeNode root)
{
// Stores count of levels, where the set
// bits of all the nodes are at
// different positions
int uniqueLevels = 0;
// Store nodes at each level of
// the tree using BFS
Queue<TreeNode> que = new LinkedList<>();
que.add(root);
// Performing level order traversal
while (que.size() > 0)
{
// Stores count of nodes at
// current level
int length = que.size();
// Stores prefix XOR of all
// the nodes at current level
int prefix_XOR = 0;
// Stores prefix OR of all
// the nodes at current level
int prefix_OR = 0;
// Check if set bit of all the nodes
// at current level is at different
// positions or not
boolean flag = true;
// Traverse nodes at current level
for(int i = 0; i < length; i++)
{
// Stores front element
// of the que
TreeNode temp = que.peek();
que.remove();
// Update prefix_OR
prefix_OR |= temp.val;
// Update prefix_XOR
prefix_XOR ^= temp.val;
if (prefix_XOR != prefix_OR)
flag = false;
// If left subtree not null
if (temp.left != null)
que.add(temp.left);
// If right subtree not null
if (temp.right != null)
que.add(temp.right);
// Update length
}
//If bitwise AND is zero
if (flag)
uniqueLevels += 1;
}
System.out.print(uniqueLevels);
}
// Driver Code
public static void main(String[] args)
{
TreeNode root = new TreeNode(5);
root.left = new TreeNode(6);
root.right = new TreeNode(9);
root.left.left = new TreeNode(1);
root.left.right = new TreeNode(4);
root.right.right = new TreeNode(7);
// Function Call
uniqueLevels(root);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python program for the above approach # Structure of a node in # the binary tree class TreeNode: def __init__(self, val = 0, left = None, right = None): self.val = val self.left = left self.right = right # Function to find total unique levels def uniqueLevels(root): # Stores count of levels, where the set # bits of all the nodes are at # different positions uniqueLevels = 0 # Store nodes at each level of # the tree using BFS que = [root] # Performing level order traversal while len(que): # Stores count of nodes at # current level length = len(que) # Stores prefix XOR of all # the nodes at current level prefix_XOR = 0; # Stores prefix OR of all # the nodes at current level prefix_OR = 0 # Check if set bit of all the nodes # at current level is at different # positions or not flag = True # Traverse nodes at current level while length: # Stores front element # of the que temp = que.pop(0) # Update prefix_OR prefix_OR |= temp.val # Update prefix_XOR prefix_XOR ^= temp.val if prefix_XOR != prefix_OR: flag = False # If left subtree not NULL if temp.left: que.append(temp.left) # If right subtree not NULL if temp.right: que.append(temp.right) # Update length length -= 1 # If bitwise AND is zero if flag: uniqueLevels += 1 print(uniqueLevels) # Driver Code if __name__ == '__main__': root = TreeNode(5) root.left = TreeNode(6) root.right = TreeNode(9) root.left.left = TreeNode(1) root.left.right = TreeNode(4) root.right.right = TreeNode(7) # Function Call uniqueLevels(root)
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG
{
// Structure of a node in
// the binary tree
class TreeNode
{
public int val = 0;
public TreeNode left, right;
public TreeNode(int x)
{
val = x;
left = null;
right = null;
}
};
// Function to find total unique levels
static void uniqueLevels(TreeNode root)
{
// Stores count of levels, where the set
// bits of all the nodes are at
// different positions
int uniqueLevels = 0;
// Store nodes at each level of
// the tree using BFS
Queue<TreeNode> que = new Queue<TreeNode>();
que.Enqueue(root);
// Performing level order traversal
while (que.Count > 0)
{
// Stores count of nodes at
// current level
int length = que.Count;
// Stores prefix XOR of all
// the nodes at current level
int prefix_XOR = 0;
// Stores prefix OR of all
// the nodes at current level
int prefix_OR = 0;
// Check if set bit of all the nodes
// at current level is at different
// positions or not
bool flag = true;
// Traverse nodes at current level
for(int i = 0; i < length; i++)
{
// Stores front element
// of the que
TreeNode temp = que.Peek();
que.Dequeue();
// Update prefix_OR
prefix_OR |= temp.val;
// Update prefix_XOR
prefix_XOR ^= temp.val;
if (prefix_XOR != prefix_OR)
flag = false;
// If left subtree not null
if (temp.left != null)
que.Enqueue(temp.left);
// If right subtree not null
if (temp.right != null)
que.Enqueue(temp.right);
// Update length
}
//If bitwise AND is zero
if (flag)
uniqueLevels += 1;
}
Console.Write(uniqueLevels);
}
// Driver Code
public static void Main(String[] args)
{
TreeNode root = new TreeNode(5);
root.left = new TreeNode(6);
root.right = new TreeNode(9);
root.left.left = new TreeNode(1);
root.left.right = new TreeNode(4);
root.right.right = new TreeNode(7);
// Function Call
uniqueLevels(root);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program for the above approach
// Structure of a node in
// the binary tree
class TreeNode
{
constructor(x)
{
this.val = x;
this.left = null;
this.right = null;
}
}
// Function to find total unique levels
function uniqueLevels(root)
{
// Stores count of levels, where the set
// bits of all the nodes are at
// different positions
let uniqueLevels = 0;
// Store nodes at each level of
// the tree using BFS
let que = [];
que.push(root);
// Performing level order traversal
while (que.length > 0)
{
// Stores count of nodes at
// current level
let length = que.length;
// Stores prefix XOR of all
// the nodes at current level
let prefix_XOR = 0;
// Stores prefix OR of all
// the nodes at current level
let prefix_OR = 0;
// Check if set bit of all the nodes
// at current level is at different
// positions or not
let flag = true;
// Traverse nodes at current level
for(let i = 0; i < length; i++)
{
// Stores front element
// of the que
let temp = que[0];
que.shift();
// Update prefix_OR
prefix_OR |= temp.val;
// Update prefix_XOR
prefix_XOR ^= temp.val;
if (prefix_XOR != prefix_OR)
flag = false;
// If left subtree not null
if (temp.left != null)
que.push(temp.left);
// If right subtree not null
if (temp.right != null)
que.push(temp.right);
}
// If bitwise AND is zero
if (flag)
uniqueLevels += 1;
}
document.write(uniqueLevels);
}
// Driver Code
let root = new TreeNode(5);
root.left = new TreeNode(6);
root.right = new TreeNode(9);
root.left.left = new TreeNode(1);
root.left.right = new TreeNode(4);
root.right.right = new TreeNode(7);
// Function Call
uniqueLevels(root);
// This code is contributed by unknown2108
</script>
Producción:
2
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