Vista izquierda y derecha de un árbol genérico

Dado un árbol genérico que consta de N Nodes, la tarea es encontrar las vistas izquierda y derecha del árbol genérico dado.

Ejemplos:

Entrada:              
            1           
      / \      
    2 3    
  / \ / \ \
4 5 6 7 8

Salida:
Vista izquierda: 1 2 4 
Vista derecha: 1 3 8 
Explicación:
Cuando el árbol se ve desde el lado izquierdo, los Nodes visibles son 1 2 4.
Cuando el árbol se ve desde el lado derecho, los Nodes que son visibles es 1 3 8.

Entrada:
           1           
      / \      
    2 3    
     \ / \
      4 5 6
       \
        7
Salida: 
Vista izquierda: 1 2 4 7 
Vista derecha: 1 3 6 7 

Enfoque: el problema dado se puede resolver utilizando el concepto de recorrido de orden de nivel del árbol . En esto, el recorrido del árbol se realiza de forma ordenada por niveles. Después de almacenar todos los Nodes en el recorrido de orden de nivel, está claro que en la vista izquierda del árbol está el primer Node de todos los niveles y, de manera similar, en la vista derecha del árbol está el último Node de todos los niveles comenzando desde la raíz.

Por lo tanto, después de almacenar el recorrido de orden de niveles, primero imprima todos los primeros Nodes almacenados en cada nivel para la Vista izquierda e imprima todos los últimos Nodes almacenados en cada nivel para la Vista derecha .

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Structure of Node
struct Node {
    int val;
    vector<Node*> child;
};
 
// Utility function to create a
// new tree node
Node* newNode(int key)
{
    Node* temp = new Node;
    temp->val = key;
    return temp;
}
 
// Function to get the left view and
// right view of the given tree
void getLeftRightview(Node* root)
{
    // Stores the nodes of each level
    queue<Node*> curNodes;
 
    // Push the root to initiate the
    // level ordered traversal
    curNodes.push(root);
 
    // Stores the left and right views
    vector<int> leftView, rightView;
 
    // Iterate until queue is non-empty
    while (!curNodes.empty()) {
 
        // Find the number of ndoes in
        // current level
        int n = curNodes.size();
 
        for (int i = 0; i < n; i++) {
            Node* cur = curNodes.front();
            curNodes.pop();
 
            // If the node is first node
            // in the level
            if (i == 0)
                leftView.push_back(
                    cur->val);
 
            // If the node is last node
            // in the level
            if (i == n - 1)
                rightView.push_back(
                    cur->val);
 
            // Push all the childs of the
            // current node into the queue
            for (int it = 0;
                 it < cur->child.size(); it++) {
                curNodes.push(
                    cur->child[it]);
            }
        }
    }
 
    // Print the left view
    cout << "Left View: ";
    for (int i = 0; i < leftView.size(); i++)
        cout << leftView[i] << ' ';
    cout << endl;
 
    // Print the right view
    cout << "RIght View: ";
    for (int i = 0; i < rightView.size(); i++)
        cout << rightView[i] << ' ';
}
 
// Driver Code
int main()
{
    Node* root = newNode(1);
    (root->child).push_back(newNode(2));
    (root->child).push_back(newNode(3));
    (root->child[0]->child).push_back(newNode(4));
    (root->child[1]->child).push_back(newNode(6));
    (root->child[0]->child).push_back(newNode(5));
    (root->child[1])->child.push_back(newNode(7));
    (root->child[1]->child).push_back(newNode(8));
 
    getLeftRightview(root);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
public class Main
{
   
    // Structure of Node
    static class Node {
         
        public int val;
        public Vector<Node> child;
         
        public Node(int key)
        {
            val = key;
            child = new Vector<Node>();
        }
    }
     
    // Utility function to create a
    // new tree node
    static Node newNode(int key)
    {
        Node temp = new Node(key);
        return temp;
    }
       
    // Function to get the left view and
    // right view of the given tree
    static void getLeftRightview(Node root)
    {
        // Stores the nodes of each level
        Vector<Node> curNodes = new Vector<Node>();
       
        // Push the root to initiate the
        // level ordered traversal
        curNodes.add(root);
       
        // Stores the left and right views
        Vector<Integer> leftView = new Vector<Integer>();
        Vector<Integer> rightView = new Vector<Integer>();
       
        // Iterate until queue is non-empty
        while (curNodes.size() > 0) {
       
            // Find the number of ndoes in
            // current level
            int n = curNodes.size();
       
            for (int i = 0; i < n; i++) {
                Node cur = (Node)curNodes.get(0);
                curNodes.remove(0);
       
                // If the node is first node
                // in the level
                if (i == 0)
                    leftView.add(cur.val);
       
                // If the node is last node
                // in the level
                if (i == n - 1)
                    rightView.add(cur.val);
       
                // Push all the childs of the
                // current node into the queue
                for (int it = 0; it < cur.child.size(); it++) {
                    curNodes.add(cur.child.get(it));
                }
            }
        }
       
        // Print the left view
        System.out.print("Left View: ");
        for (int i = 0; i < leftView.size(); i++)
            System.out.print(leftView.get(i) + " ");
        System.out.println();
       
        // Print the right view
        System.out.print("RIght View: ");
        for (int i = 0; i < rightView.size(); i++)
            System.out.print(rightView.get(i) + " ");
    }
     
    public static void main(String[] args) {
        Node root = newNode(1);
        (root.child).add(newNode(2));
        (root.child).add(newNode(3));
        (root.child.get(0).child).add(newNode(4));
        (root.child.get(1).child).add(newNode(6));
        (root.child.get(0).child).add(newNode(5));
        (root.child.get(1)).child.add(newNode(7));
        (root.child.get(1).child).add(newNode(8));
       
        getLeftRightview(root);
    }
}
 
// This code is contributed by divyeshrabadiya07.

# Python3 implementation for the above approach
import sys
 
# Structure of Node
class Node:
    def __init__(self, key):
        self.val = key
        self.child = []
 
# Utility function to create a
# new tree node
def newNode(key):
    temp = Node(key)
    return temp
 
# Function to get the left view and
# right view of the given tree
def getLeftRightview(root):
    # Stores the nodes of each level
    curNodes = []
 
    # Push the root to initiate the
    # level ordered traversal
    curNodes.append(root)
 
    # Stores the left and right views
    leftView, rightView = [], []
 
    # Iterate until queue is non-empty
    while (len(curNodes) != 0):
        # Find the number of ndoes in
        # current level
        n = len(curNodes)
 
        for i in range(n):
            cur = curNodes[0]
            curNodes.pop(0)
 
            # If the node is first node
            # in the level
            if (i == 0):
                leftView.append(cur.val)
 
            # If the node is last node
            # in the level
            if (i == n - 1):
                rightView.append(cur.val)
 
            # Push all the childs of the
            # current node into the queue
            for it in range(len(cur.child)):
                curNodes.append(cur.child[it])
 
    # Print the left view
    print("Left View: ", end = "")
    for i in range(len(leftView)):
        print(leftView[i], "", end = "")
    print()
 
    # Print the right view
    print("RIght View: ", end = "")
    for i in range(len(rightView)):
        print(rightView[i], "", end = "")
 
root = newNode(1)
(root.child).append(newNode(2))
(root.child).append(newNode(3))
(root.child[0].child).append(newNode(4))
(root.child[1].child).append(newNode(6))
(root.child[0].child).append(newNode(5))
(root.child[1]).child.append(newNode(7))
(root.child[1].child).append(newNode(8))
 
getLeftRightview(root)
 
# This code is contributed by rameshtravel07.

// C# program for the above approach
using System;
using System.Collections;
using System.Collections.Generic;
class GFG {
     
    // Structure of Node
    class Node {
        
        public int val;
        public List<Node> child;
        
        public Node(int key)
        {
            val = key;
            child = new List<Node>();
        }
    }
     
    // Utility function to create a
    // new tree node
    static Node newNode(int key)
    {
        Node temp = new Node(key);
        return temp;
    }
      
    // Function to get the left view and
    // right view of the given tree
    static void getLeftRightview(Node root)
    {
        // Stores the nodes of each level
        Queue curNodes = new Queue();
      
        // Push the root to initiate the
        // level ordered traversal
        curNodes.Enqueue(root);
      
        // Stores the left and right views
        List<int> leftView = new List<int>();
        List<int> rightView = new List<int>();
      
        // Iterate until queue is non-empty
        while (curNodes.Count > 0) {
      
            // Find the number of ndoes in
            // current level
            int n = curNodes.Count;
      
            for (int i = 0; i < n; i++) {
                Node cur = (Node)curNodes.Peek();
                curNodes.Dequeue();
      
                // If the node is first node
                // in the level
                if (i == 0)
                    leftView.Add(cur.val);
      
                // If the node is last node
                // in the level
                if (i == n - 1)
                    rightView.Add(cur.val);
      
                // Push all the childs of the
                // current node into the queue
                for (int it = 0; it < cur.child.Count; it++) {
                    curNodes.Enqueue(cur.child[it]);
                }
            }
        }
      
        // Print the left view
        Console.Write("Left View: ");
        for (int i = 0; i < leftView.Count; i++)
            Console.Write(leftView[i] + " ");
        Console.WriteLine();
      
        // Print the right view
        Console.Write("RIght View: ");
        for (int i = 0; i < rightView.Count; i++)
            Console.Write(rightView[i] + " ");
    }
     
  static void Main() {
    Node root = newNode(1);
    (root.child).Add(newNode(2));
    (root.child).Add(newNode(3));
    (root.child[0].child).Add(newNode(4));
    (root.child[1].child).Add(newNode(6));
    (root.child[0].child).Add(newNode(5));
    (root.child[1]).child.Add(newNode(7));
    (root.child[1].child).Add(newNode(8));
  
    getLeftRightview(root);
  }
}
 
// This code is contributed by mukesh07.

<script>
    // Javascript program for the above approach
     
    // Structure of Node
    class Node
    {
        constructor(key) {
           this.val = key;
           this.child = [];
        }
    }
     
    // Utility function to create a
    // new tree node
    function newNode(key)
    {
        let temp = new Node(key);
        return temp;
    }
 
    // Function to get the left view and
    // right view of the given tree
    function getLeftRightview(root)
    {
        // Stores the nodes of each level
        let curNodes = [];
 
        // Push the root to initiate the
        // level ordered traversal
        curNodes.push(root);
 
        // Stores the left and right views
        let leftView = [], rightView = [];
 
        // Iterate until queue is non-empty
        while (curNodes.length != 0) {
 
            // Find the number of ndoes in
            // current level
            let n = curNodes.length;
 
            for (let i = 0; i < n; i++) {
                let cur = curNodes[0];
                curNodes.shift();
 
                // If the node is first node
                // in the level
                if (i == 0)
                    leftView.push(cur.val);
 
                // If the node is last node
                // in the level
                if (i == n - 1)
                    rightView.push(cur.val);
 
                // Push all the childs of the
                // current node into the queue
                for (let it = 0; it < cur.child.length; it++) {
                    curNodes.push(cur.child[it]);
                }
            }
        }
 
        // Print the left view
        document.write("Left View: ");
        for (let i = 0; i < leftView.length; i++)
            document.write(leftView[i] + " ");
        document.write("</br>");
 
        // Print the right view
        document.write("RIght View: ");
        for (let i = 0; i < rightView.length; i++)
            document.write(rightView[i] + " ");
    }
     
    let root = newNode(1);
    (root.child).push(newNode(2));
    (root.child).push(newNode(3));
    (root.child[0].child).push(newNode(4));
    (root.child[1].child).push(newNode(6));
    (root.child[0].child).push(newNode(5));
    (root.child[1]).child.push(newNode(7));
    (root.child[1].child).push(newNode(8));
   
    getLeftRightview(root);
 
// This code is contributed by decode2207.
</script>

Left View: 1 2 4 
RIght View: 1 3 8

Complejidad temporal: O(N)
Espacio auxiliar: O(N)