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