Dado un árbol binario completo de profundidad H . Si se toma la imagen especular del lado izquierdo y derecho de este árbol, entonces:
Imagen reflejada a la derecha: el Node más a la derecha de cada nivel está conectado al Node correspondiente reflejado.
Imagen reflejada izquierda: el Node más a la izquierda de cada nivel está conectado al Node correspondiente reflejado.
La tarea es encontrar el número de aristas después de tomar ambas imágenes especulares en el árbol final.
Ejemplos:
Entrada: H = 1
Salida: 10
2 aristas en el árbol original se reflejarán en las imágenes especulares (izquierda y derecha), es decir, 6 aristas en total.
Y los bordes que conectan las imágenes especulares con el árbol original como se muestra en la imagen de arriba.
Entrada: H = 2
Salida: 24
(6 * 3) + 3 + 3 = 24
Enfoque: mantenga los Nodes más a la izquierda y más a la derecha después de cada imagen especular. El número de bordes cambiará después de cada operación de imagen especular. Inicialmente,
Después de la imagen reflejada derecha:
Después de la imagen reflejada izquierda:
En árbol completo modificado:
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to return the total number // of edges in the modified tree int countEdges(int H) { int edges, right, left; edges = 2 * (pow(2, H) - 1); left = right = H + 1; // Total edges in the modified tree int cnt = (edges * 3) + left + right; return cnt; } // Driver code int main() { int H = 1; cout << countEdges(H); return 0; }
Java
// Java implementation of the approach import java.io.*; class GFG { // Function to return the total number // of edges in the modified tree static int countEdges(int H) { int edges, right, left; edges = 2 * (int)(Math.pow(2, H) - 1); left = right = H + 1; // Total edges in the modified tree int cnt = (edges * 3) + left + right; return cnt; } // Driver code public static void main(String[] args) { int H = 1; System.out.println(countEdges(H)); } } // This code has been contributed by anuj_67..
Python 3
# Python 3 implementation of the approach # Function to return the total number # of edges in the modified tree def countEdges( H): edges = 2 * (pow(2, H) - 1) left = right = H + 1 # Total edges in the modified tree cnt = (edges * 3) + left + right return cnt # Driver code if __name__ == "__main__": H = 1; print(countEdges(H)) # This code is contributed by ChitraNayal
C#
// C# implementation of the approach using System; class GFG { // Function to return the total number // of edges in the modified tree static int countEdges(int H) { int edges, right, left; edges = 2 * (int)(Math.Pow(2, H) - 1); left = right = H + 1; // Total edges in the modified tree int cnt = (edges * 3) + left + right; return cnt; } // Driver code public static void Main() { int H = 1; Console.WriteLine(countEdges(H)); } } // This code is contributed by AnkitRai01
Javascript
<script> // Javascript implementation of the approach // Function to return the total number // of edges in the modified tree function countEdges(H) { let edges, right, left; edges = 2 * (Math.pow(2, H) - 1); left = right = H + 1; // Total edges in the modified tree let cnt = (edges * 3) + left + right; return cnt; } let H = 1; document.write(countEdges(H)); </script>
10
Publicación traducida automáticamente
Artículo escrito por SURENDRA_GANGWAR y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA