Dada la raíz de un árbol binario en el que todos los Nodes tienen valores 0 o 1 , la tarea es encontrar e imprimir todos los niveles para los que existe otro nivel de modo que la representación decimal de cada uno sea la misma. Si no existe tal nivel, devuelve una lista vacía.
Ejemplos:
Entrada:
1
/ \
0 1
/ \ /
1 0 1
/ \
0 1
/
1
Salida: {3, 1}, {4, 0}
Explicación: el nivel 3 es un duplicado del nivel 1
El nivel 4 es un duplicado del nivel 0Entrada: 1
Salida: { }
Planteamiento: La idea para resolver el problema se basa en la siguiente observación:
La idea es realizar un recorrido por orden de niveles de un árbol determinado y, para cada nivel, convertir la representación binaria a decimal y almacenarla en una variable int. Luego, el problema se convertirá para simplemente encontrar todos los elementos duplicados en la array dada .
Siga los pasos a continuación para resolver este problema:
- Hacer un recorrido de orden de nivel desde la raíz hasta la hoja
- Para cada nivel, conviértalo al equivalente decimal y almacene el valor en un mapa en formato {decimal_number, level_number} .
- Luego, simplemente verifique si hay más de un nivel para una clave decimal.
- En caso afirmativo, imprima los niveles como duplicados.
- Si no existe tal nivel, devuelve una lista vacía.
A continuación se muestra la implementación del enfoque anterior:
C#
// C# program to implement above approach
using System;
using System.Collections.Generic;
using System.Linq;
// Class containing left and right
// child of current node and key value
public class Node {
public int data;
public Node left, right;
public Node(int item)
{
data = item;
left = right = null;
}
}
public class LevelInfo {
public int level;
public int length;
}
public class GFG {
// Root of the Binary Tree
public Node root;
Dictionary<int, List<LevelInfo> > duplicateMap
= new Dictionary<int, List<LevelInfo> >();
public virtual List<List<int> >
printDuplicateLevels(Node root)
{
int h = height(root);
int i;
List<List<int> > dup_levels
= new List<List<int> >();
// Initialize for the root level
var zerolevelInfo
= new LevelInfo() { level = 0,
length = 0 };
duplicateMap[root.data]
= new List<LevelInfo>() { zerolevelInfo };
for (i = 1; i <= h; i++) {
List<int> currentLevel
= new List<int>();
var currentLevelOrder
= getCurrentLevel(root, i,
currentLevel)
.ToList();
int decimalValue = Convert.ToInt32(
string.Join("", currentLevelOrder), 2);
var currentlevelInfo = new LevelInfo() {
level = i - 1, length
= currentLevelOrder.Count()
};
if (duplicateMap.ContainsKey(decimalValue)) {
var dictData
= duplicateMap[decimalValue].Where(
l => l.length
== currentLevelOrder.Count());
if (dictData.Any()) {
List<int> dup_level_curr
= new List<int>();
dup_level_curr.Add(i - 1);
dup_level_curr.Add(
dictData.Select(l => l.level)
.First());
dup_levels.Add(dup_level_curr);
}
else {
duplicateMap[decimalValue].Add(
currentlevelInfo);
}
}
else
duplicateMap[decimalValue]
= new List<LevelInfo>() {
currentlevelInfo
};
}
return dup_levels;
}
// Compute the "height" of a tree
public virtual int height(Node root)
{
if (root == null) {
return 0;
}
else {
// Compute height of each subtree
int lheight = height(root.left);
int rheight = height(root.right);
// Use the larger one
if (lheight > rheight) {
return (lheight + 1);
}
else {
return (rheight + 1);
}
}
}
// Get nodes at the current level
public virtual IList<int>
getCurrentLevel(Node root, int level,
List<int> currentLevelOrder)
{
if (root == null) {
return currentLevelOrder;
}
if (level == 1) {
currentLevelOrder.Add(root.data);
}
else if (level > 1) {
getCurrentLevel(root.left, level - 1,
currentLevelOrder);
getCurrentLevel(root.right, level - 1,
currentLevelOrder);
}
return currentLevelOrder;
}
// Driver Code
public static void Main(string[] args)
{
GFG tree = new GFG();
tree.root = new Node(1);
tree.root.left = new Node(0);
tree.root.right = new Node(1);
tree.root.left.left = new Node(1);
tree.root.left.right = new Node(0);
tree.root.right.left = new Node(1);
tree.root.left.right.left = new Node(0);
tree.root.right.left.right = new Node(1);
tree.root.left.right.left.left = new Node(1);
// Execute and print the duplicate levels
List<List<int> > dup_levels
= tree.printDuplicateLevels(tree.root);
Console.Write("[ ");
foreach(var curr_level in dup_levels)
{
Console.Write("[ ");
foreach(var dupli_level in curr_level)
{
Console.Write(dupli_level + " ");
}
Console.Write("] ");
}
Console.WriteLine("]");
}
}
[ [ 3 1 ] [ 4 0 ] ]
Complejidad temporal: O(N)
Espacio auxiliar: O(N)