Dado un árbol binario, la tarea es imprimir la capa del cono exterior, es decir, una combinación de capas formadas moviéndose solo a través del hijo izquierdo desde la raíz y la capa moviéndose solo a través del hijo derecho desde la raíz. Imprima la capa izquierda de forma ascendente y la capa derecha de forma descendente.
Ejemplos:
Entrada: 12
/ \
15 65
/ \ / \
9 10 45 57
Salida: 9 15 12 65 57
Explicación: La capa izquierda es 12, 15, 9.
De abajo hacia arriba es 9 15 12.
La capa derecha es 65, 57.
Entonces, la capa general es 9, 15, 12, 65, 57.Entrada: 12
/
4
/
5
\
3
/
1
Salida: 5 4 12.
Explicación: La capa izquierda que se mueve solo a través del niño izquierdo es 12, 4, 5.
Entonces, la capa del cono es 5 4 12
Planteamiento: El problema se puede resolver a partir de la siguiente idea:
Encuentre la vista izquierda del árbol hasta que pueda moverse solo a través del niño izquierdo. De manera similar, encuentre la vista correcta del árbol hasta que pueda moverse solo a través del niño correcto. Luego imprímelos como se menciona en el problema.
Siga los pasos mencionados a continuación para implementar la idea:
Paso 1: Primero intente obtener la vista más a la izquierda del árbol de modo que en cualquier nivel, si hay un Node que es el hijo correcto, entonces no deberíamos tomar eso .
Motivo: Considere el siguiente árbol:
12
/
4
/
5
\
3
/
1Si intenta encontrar la vista izquierda del árbol que se muestra arriba, obtendrá 12, 4, 5, 3, 1 como respuesta. Pero de acuerdo con nuestro enunciado del problema, no necesitamos 3 y 1.
Paso 2: una vez que obtenga la vista izquierda del paso 1 , invierta los valores de la vista izquierda para obtenerla de abajo hacia arriba.
Paso 3: intente obtener la vista más a la derecha del árbol de modo que, en cualquier nivel, si hay un Node que es un hijo izquierdo, no tome ese Node en la vista derecha. (La razón es similar al paso 1 porque puede incorporar Nodes que no son necesarios).
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Structure of a binary tree node struct Node { int data; struct Node *left, *right; }; // Function to create a new tree node Node* newNode(int data) { Node* temp = new Node; temp->data = data; temp->left = temp->right = nullptr; return temp; } int maxLevel = 0; // Function to find the leftview void leftView(Node* root, int level, vector<int>& ans) { if (!root) return; if (maxLevel < level) { ans.push_back(root->data); maxLevel = level; } leftView(root->left, level + 1, ans); } // Function to find the rightview void rightView(Node* root, int level, vector<int>& ans) { if (!root) return; if (maxLevel < level) { ans.push_back(root->data); maxLevel = level; } rightView(root->right, level + 1, ans); } // Function to print the traversal vector<int> coneLevel(Node* root) { maxLevel = 0; // Vector in which we will store // the boundary of the binary tree vector<int> ans; // Calling the leftView If you have notices // that we are passing the root->left because // we are considering the root value // in the rightView call leftView(root->left, 1, ans); // We need to reverse the solution because // of the reason stated in step 2 reverse(ans.begin(), ans.end()); // Again setting the value of maxLevel as zero maxLevel = 0; // Calling the rightView in this call we are // considering the root value rightView(root, 1, ans); return ans; } // Driver code int main() { Node* root = newNode(12); root->left = newNode(15); root->right = newNode(65); root->left->left = newNode(9); root->left->right = newNode(10); root->right->left = newNode(46); root->right->right = newNode(57); // Function call vector<int> ans = coneLevel(root); // Printing the solution for (auto it : ans) cout << it << " "; return 0; }
Java
// Java code to implement the approach import java.io.*; import java.util.*; class GFG { // Structure of a binary tree node public static class Node { int data; Node left; Node right; Node() {} Node(int data) { this.data = data; } Node(int data, Node left, Node right) { this.data = data; this.left = left; this.right = right; } } static int maxLevel = 0; // Function to find the leftview public static void leftView(Node root, int level, ArrayList<Integer> ans) { if (root == null) return; if (maxLevel < level) { ans.add(root.data); maxLevel = level; } leftView(root.left, level + 1, ans); } // Function to find the rightview public static void rightView(Node root, int level, ArrayList<Integer> ans) { if (root == null) return; if (maxLevel < level) { ans.add(root.data); maxLevel = level; } rightView(root.right, level + 1, ans); } // Function to print the traversal public static ArrayList<Integer> coneLevel(Node root) { maxLevel = 0; // ArrayList in which we will store // the boundary of the binary tree ArrayList<Integer> ans = new ArrayList<>(); // Calling the leftView If you have noticed // that we are passing the root->left because // we are considering the root value // in the rightView call leftView(root.left, 1, ans); // We need to reverse the solution because // of the reason stated in step 2 Collections.reverse(ans); // Again setting the value of maxLevel as zero maxLevel = 0; // Calling the rightView in this call we are // considering the root value rightView(root, 1, ans); return ans; } // Driver Code public static void main(String[] args) { Node root = new Node(12); root.left = new Node(15); root.right = new Node(65); root.left.left = new Node(9); root.left.right = new Node(10); root.right.left = new Node(46); root.right.right = new Node(57); // Function call ArrayList<Integer> ans = coneLevel(root); // Printing the solution for (Integer it : ans) System.out.print(it + " "); } } // This code is contributed by Rohit Pradhan
Python3
# Python3 code to implement the approach # Structure of a binary tree node class Node: def __init__(self,data = 0,left = None,right = None): self.data = data self.left = left self.right = right maxLevel = 0 # Function to find the leftview def leftView(root,level,ans): global maxLevel if (root == None): return if (maxLevel < level): ans.append(root.data) maxLevel = level leftView(root.left, level + 1, ans) # Function to find the rightview def rightView(root,level,ans): global maxLevel if (root == None): return if (maxLevel < level): ans.append(root.data) maxLevel = level rightView(root.right, level + 1, ans) # Function to print the traversal def coneLevel(root): global maxLevel maxLevel = 0 # ArrayList in which we will store # the boundary of the binary tree ans = [] # Calling the leftView If you have noticed # that we are passing the root->left because # we are considering the root value # in the rightView call leftView(root.left, 1, ans) # We need to reverse the solution because # of the reason stated in step 2 ans = ans[::-1] # Again setting the value of maxLevel as zero maxLevel = 0 # Calling the rightView in this call we are # considering the root value rightView(root, 1, ans) return ans # Driver Code root = Node(12) root.left = Node(15) root.right = Node(65) root.left.left = Node(9) root.left.right = Node(10) root.right.left = Node(46) root.right.right = Node(57) # Function call ans = coneLevel(root) # Printing the solution for it in ans: print(it ,end = " ") # This code is contributed by shinjanpatra
Javascript
<script> // JavaScript code to implement the approach // Structure of a binary tree node class Node{ constructor(data = 0,left = null,right = null){ this.data = data this.left = left this.right = right } } let maxLevel = 0 // Function to find the leftview function leftView(root,level,ans){ if (root == null) return if (maxLevel < level){ ans.push(root.data) maxLevel = level } leftView(root.left, level + 1, ans) } // Function to find the rightview function rightView(root,level,ans){ if (root == null) return if (maxLevel < level){ ans.push(root.data) maxLevel = level } rightView(root.right, level + 1, ans) } // Function to print the traversal function coneLevel(root){ maxLevel = 0 // ArrayList in which we will store // the boundary of the binary tree let ans = [] // Calling the leftView If you have noticed // that we are passing the root->left because // we are considering the root value // in the rightView call leftView(root.left, 1, ans) // We need to reverse the solution because // of the reason stated in step 2 ans = ans.reverse(); // Again setting the value of maxLevel as zero maxLevel = 0 // Calling the rightView in this call we are // considering the root value rightView(root, 1, ans) return ans } // Driver Code let root = new Node(12) root.left = new Node(15) root.right = new Node(65) root.left.left = new Node(9) root.left.right = new Node(10) root.right.left = new Node(46) root.right.right = new Node(57) // Function call let ans = coneLevel(root) // Printing the solution for(let it of ans) document.write(it ," ") // This code is contributed by shinjanpatra </script>
9 15 12 65 57
Complejidad Temporal: O(V + E), donde V son los vértices y E las aristas
Espacio Auxiliar: O(V)
Publicación traducida automáticamente
Artículo escrito por adityakumar129 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA