Imprime la capa exterior del cono.

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
               /
             1

Si 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>
Producción

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *