Dado un árbol binario que consta de 1 o 0 como valores de Node, la tarea es encontrar la suma de todos los niveles verticales del árbol binario , considerando cada valor como una representación binaria.
Ejemplos:
Entrada: 1
/ \
1 0
/ \ / \
1 0 1 0
Salida: 7
Explicación:
Tomando niveles verticales de izquierda a derecha:
Para nivel vertical 1: (1) 2 = 1
Para nivel vertical 2: (1) 2 = 1
Para nivel vertical 3: (101) 2 = 5
Para nivel vertical 4: (0) 2 = 0
Para nivel vertical 5: (0) 2 = 0
Suma total = 1+1+5+0+0 = 7Entrada: 0
/ \
1 0
/ \ \
1 1 0
/ \ \ / \
1 1 1 0 0
Salida: 8
Explicación:
Tomando niveles verticales de izquierda a derecha: Para el nivel vertical 1: (1) 2 = 1 Para el nivel vertical 2: (1) 2 = 1 Para nivel vertical 3: (11) 2 = 3 Para nivel vertical 4: (01) 2 = 1 Para nivel vertical 5: (010) 2 = 2 Para nivel vertical 6: (0) 2 = 0 Para el nivel vertical 7: (0)
2 = 0
Suma total = 1+1+3+1+2+0+0 = 8
Enfoque: siga los pasos a continuación para resolver el problema:
- Realice un recorrido de árbol mientras realiza un seguimiento de la distancia horizontal y vertical desde el Node raíz
- Almacene el valor del Node correspondiente a su distancia horizontal en un Hashmap .
- Inicialice una variable, digamos ans , para almacenar el resultado requerido.
- Cree un Hashmap , digamos M , para almacenar la distancia horizontal como clave y una array de pares {valor del Node, distancia del Node desde la raíz} .
- La altura de cada Node también se almacena, ya que se necesita que el nivel vertical esté ordenado (de arriba a abajo) para obtener el valor decimal correcto de su representación binaria.
- Realice el recorrido del árbol de preorden y también pase la altura vertical y las distancias horizontales como parámetros.
- Si la raíz no es NULL , realice las siguientes operaciones:
- Agregue el par {valor de Node, altura vertical en la distancia horizontal} en M .
- Atraviese el subárbol izquierdo , reduciendo la distancia horizontal en 1 .
- Atraviese el subárbol derecho , incrementando la distancia horizontal en 1 .
- Incremente la altura vertical en 1 para ambas llamadas recursivas.
- Si la raíz no es NULL , realice las siguientes operaciones:
- Ahora, recorra el Hashmap , diga M y para cada tecla, realice los siguientes pasos:
- Ordene los valores en función de su altura desde el Node raíz y luego convierta el número binario obtenido a su equivalente decimal y guárdelo en una variable, digamos B .
- Sume el valor de B a ans .
- Imprime el valor de ans
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for super ugly number
#include<bits/stdc++.h>
using namespace std;
// Structure of a Tree node
struct TreeNode
{
int val = 0;
TreeNode *left;
TreeNode *right;
TreeNode(int x)
{
val = x;
left = right = NULL;
}
};
// Function to convert
// binary number to decimal
int getDecimal(vector<pair<int, int> > arr)
{
// Sort the array on
// the basis of the
// first index i.e, height
sort(arr.begin(), arr.end());
// Store the required
// decimal equivalent
// of the number
int ans = 0;
// Traverse the array
for (int i = 0; i < arr.size(); i++)
{
ans <<= 1;
ans |= arr[i].second;
}
// Return the answer
return ans;
}
// Function to traverse the tree
void Traverse(TreeNode *root, int hd, int ht,
map<int, vector<pair<int, int> > > &mp)
{
// If root is NULL, return
if (!root)
return;
mp[hd].push_back({ht, root->val});
// Make recursive calls to the left and
// right subtree
Traverse(root->left, hd - 1, ht + 1, mp);
Traverse(root->right, hd + 1, ht + 1, mp);
}
// Function to calculate
// sum of vertical levels
// of a Binary Tree
void getSum(TreeNode *root)
{
// Dictionary to store the
// vertical level as key and
// its corresponding
// binary number as value
map<int,vector<pair<int,int> > > mp;
// Function Call to perform traverse the tree
Traverse(root, 0, 0, mp);
// Store the required answer
int ans = 0;
// Get decimal values for each vertical level
// and add it to ans
for (auto i:mp)
ans += getDecimal(i.second);
// Print the answer
cout<<(ans);
}
/* Driver program to test above functions */
int main()
{
TreeNode *root = new TreeNode(1);
root->left = new TreeNode(1);
root->right = new TreeNode(0);
root->left->left = new TreeNode(1);
root->left->right = new TreeNode(0);
root->right->left = new TreeNode(1);
root->right->right = new TreeNode(0);
// Function call to get the
// sum of vertical level
// of the tree
getSum(root);
return 0;
}
// This code is contributed by mohit kumar 29.
Java
// Java program for super ugly number
import java.io.*;
import java.util.*;
// Structure of a Tree node
class TreeNode
{
int val = 0;
TreeNode left;
TreeNode right;
TreeNode(int x)
{
val = x;
left = right = null;
}
}
class GFG {
static Map<Integer, ArrayList<ArrayList<Integer>>> mp = new HashMap<Integer, ArrayList<ArrayList<Integer>>>();
// Function to convert
// binary number to decimal
static int getDecimal(ArrayList<ArrayList<Integer> > arr)
{
// Sort the array on
// the basis of the
// first index i.e, height
Collections.sort(arr, new Comparator<ArrayList<Integer>>() {
@Override
public int compare(ArrayList<Integer> o1, ArrayList<Integer> o2) {
return o1.get(0).compareTo(o2.get(0));
}
});
// Store the required
// decimal equivalent
// of the number
int ans = 0;
// Traverse the array
for (int i = 0; i < arr.size(); i++)
{
ans <<= 1;
ans |= arr.get(i).get(1);
}
// Return the answer
return ans;
}
// Function to traverse the tree
static void Traverse(TreeNode root, int hd, int ht)
{
// If root is NULL, return
if (root == null)
return;
if(mp.containsKey(hd))
{
mp.get(hd).add(new ArrayList<Integer>(Arrays.asList(ht, root.val)));
}
else
{
mp.put(hd,new ArrayList<ArrayList<Integer>>());
mp.get(hd).add(new ArrayList<Integer>(Arrays.asList(ht, root.val)));
}
// Make recursive calls to the left and
// right subtree
Traverse(root.left, hd - 1, ht + 1);
Traverse(root.right, hd + 1, ht + 1);
}
// Function to calculate
// sum of vertical levels
// of a Binary Tree
static void getSum(TreeNode root)
{
// Function Call to perform traverse the tree
Traverse(root, 0, 0);
// Store the required answer
int ans = 0;
// Get decimal values for each vertical level
// and add it to ans
for(Integer key : mp.keySet())
{
ans += getDecimal(mp.get(key));
}
// Print the answer
System.out.print(ans);
}
// Driver code
public static void main (String[] args)
{
TreeNode root = new TreeNode(1);
root.left = new TreeNode(1);
root.right = new TreeNode(0);
root.left.left = new TreeNode(1);
root.left.right = new TreeNode(0);
root.right.left = new TreeNode(1);
root.right.right = new TreeNode(0);
// Function call to get the
// sum of vertical level
// of the tree
getSum(root);
}
}
// This code is contributed by avanitrachhadiya2155
Python3
# Python program
# for the above approach
# Structure of a Tree node
class TreeNode:
def __init__(self, val ='',
left = None, right = None):
self.val = val
self.left = left
self.right = right
# Function to convert
# binary number to decimal
def getDecimal(arr):
# Sort the array on
# the basis of the
# first index i.e, height
arr.sort()
# Store the required
# decimal equivalent
# of the number
ans = 0
# Traverse the array
for i in range(len(arr)):
ans <<= 1
ans |= arr[i][1]
# Return the answer
return ans
# Function to calculate
# sum of vertical levels
# of a Binary Tree
def getSum(root):
# Dictionary to store the
# vertical level as key and
# its corresponding
# binary number as value
mp = {}
# Function to traverse the tree
def Traverse(root, hd, ht):
# If root is NULL, return
if not root:
return
# Store the value in the map
if hd not in mp:
mp[hd] = [[ht, root.val]]
else:
mp[hd].append([ht, root.val])
# Make recursive calls to the left and
# right subtree
Traverse(root.left, hd - 1, ht + 1)
Traverse(root.right, hd + 1, ht + 1)
# Function Call to perform traverse the tree
Traverse(root, 0, 0)
# Store the required answer
ans = 0
# Get decimal values for each vertical level
# and add it to ans
for i in mp:
ans += getDecimal(mp[i])
# Print the answer
print(ans)
# Driver Code
# Given Tree
root = TreeNode(1)
root.left = TreeNode(1)
root.right = TreeNode(0)
root.left.left = TreeNode(1)
root.left.right = TreeNode(0)
root.right.left = TreeNode(1)
root.right.right = TreeNode(0)
# Function call to get the
# sum of vertical level
# of the tree
getSum(root)
C#
// C# program for super ugly number
using System;
using System.Linq;
using System.Collections.Generic;
// Structure of a Tree node
public class TreeNode
{
public int val = 0;
public TreeNode left, right;
public TreeNode(int x)
{
val = x;
left = right = null;
}
}
public class GFG
{
static Dictionary<int,List<List<int>>> mp =
new Dictionary<int,List<List<int>>>();
// Function to convert
// binary number to decimal
static int getDecimal(List<List<int> > arr)
{
// Sort the array on
// the basis of the
// first index i.e, height
arr.OrderBy( l => l[0]);
// Store the required
// decimal equivalent
// of the number
int ans = 0;
// Traverse the array
for (int i = 0; i < arr.Count; i++)
{
ans <<= 1;
ans |= arr[i][1];
}
// Return the answer
return ans;
}
// Function to traverse the tree
static void Traverse(TreeNode root, int hd, int ht)
{
// If root is NULL, return
if (root == null)
return;
if(mp.ContainsKey(hd))
{
mp[hd].Add(new List<int>(){ht, root.val});
}
else
{
mp.Add(hd,new List<List<int>>());
mp[hd].Add(new List<int>(){ht, root.val});
}
// Make recursive calls to the left and
// right subtree
Traverse(root.left, hd - 1, ht + 1);
Traverse(root.right, hd + 1, ht + 1);
}
// Function to calculate
// sum of vertical levels
// of a Binary Tree
static void getSum(TreeNode root)
{
// Function Call to perform traverse the tree
Traverse(root, 0, 0);
// Store the required answer
int ans = 0;
// Get decimal values for each vertical level
// and add it to ans
foreach(int key in mp.Keys)
{
ans += getDecimal(mp[key]);
}
// Print the answer
Console.Write(ans);
}
// Driver code
static public void Main ()
{
TreeNode root = new TreeNode(1);
root.left = new TreeNode(1);
root.right = new TreeNode(0);
root.left.left = new TreeNode(1);
root.left.right = new TreeNode(0);
root.right.left = new TreeNode(1);
root.right.right = new TreeNode(0);
// Function call to get the
// sum of vertical level
// of the tree
getSum(root);
}
}
// This code is contributed by rag2127
Javascript
<script>
// Javascript program for super ugly number
// Structure of a Tree node
class TreeNode
{
constructor(x)
{
this.val = x;
this.left = this.right = null;
}
}
let mp = new Map();
// Function to convert
// binary number to decimal
function getDecimal(arr)
{
arr.sort(function(a,b){return a[0]-b[0]});
// Store the required
// decimal equivalent
// of the number
let ans = 0;
// Traverse the array
for (let i = 0; i < arr.length; i++)
{
ans <<= 1;
ans |= arr[i][1];
}
// Return the answer
return ans;
}
// Function to traverse the tree
function Traverse(root, hd, ht)
{
// If root is NULL, return
if (root == null)
return;
if(mp.has(hd))
{
mp.get(hd).push([ht, root.val]);
}
else
{
mp.set(hd,[]);
mp.get(hd).push([ht, root.val]);
}
// Make recursive calls to the left and
// right subtree
Traverse(root.left, hd - 1, ht + 1);
Traverse(root.right, hd + 1, ht + 1);
}
// Function to calculate
// sum of vertical levels
// of a Binary Tree
function getSum(root)
{
// Function Call to perform traverse the tree
Traverse(root, 0, 0);
// Store the required answer
let ans = 0;
// Get decimal values for each vertical level
// and add it to ans
for(let [key, value] of mp.entries())
{
ans += getDecimal(value);
}
// Print the answer
document.write(ans);
}
// Driver code
let root = new TreeNode(1);
root.left = new TreeNode(1);
root.right = new TreeNode(0);
root.left.left = new TreeNode(1);
root.left.right = new TreeNode(0);
root.right.left = new TreeNode(1);
root.right.right = new TreeNode(0);
// Function call to get the
// sum of vertical level
// of the tree
getSum(root);
// This code is contributed by unknown2108
</script>
Producción:
7
Complejidad de tiempo: O(N * log(N))
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por rohitsingh07052 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA