Dado un árbol binario, imprima su vista izquierda. La vista izquierda de un árbol binario es un conjunto de Nodes visibles cuando el árbol se ve desde el lado izquierdo.
Ejemplos:
Input : 1
/ \
2 3
/ \ / \
4 5 6 7
Output : 1 2 4
Input : 1
/ \
2 3
\ /
4 5
\
6
/ \
7 8
Output : 1 2 4 6 7
Ya hemos discutido este problema usando el método Recursion , aquí se usa un enfoque iterativo para resolver el problema anterior.
La idea es hacer un recorrido por orden de niveles del Árbol usando una cola e imprimir el primer Node en cada nivel.
Mientras realiza el recorrido de orden de niveles, después de recorrer todos los Nodes en cada nivel, presione un delimitador NULL para marcar el final del nivel actual. Por lo tanto, realice el recorrido del orden de niveles del árbol. Imprima el primer Node en cada nivel del árbol y empuje los elementos secundarios de todos los Nodes en cada nivel de la cola hasta que se encuentre un delimitador NULL.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to print the
// left view of Binary Tree
#include <bits/stdc++.h>
using namespace std;
// A Binary Tree Node
struct node {
int data;
struct node *left, *right;
};
// A utility function to create a new
// Binary Tree node
struct node* newNode(int item)
{
struct node* temp = new node;
temp->data = item;
temp->left = NULL;
temp->right = NULL;
return temp;
}
// Utility function to print the left view of
// the binary tree
void leftViewUtil(struct node* root, queue<node*>& q)
{
if (root == NULL)
return;
// Push root
q.push(root);
// Delimiter
q.push(NULL);
while (!q.empty()) {
node* temp = q.front();
if (temp) {
// Prints first node
// of each level
cout << temp->data << " ";
// Push children of all nodes at
// current level
while (q.front() != NULL) {
// If left child is present
// push into queue
if (temp->left)
q.push(temp->left);
// If right child is present
// push into queue
if (temp->right)
q.push(temp->right);
// Pop the current node
q.pop();
temp = q.front();
}
// Push delimiter
// for the next level
q.push(NULL);
}
// Pop the delimiter of
// the previous level
q.pop();
}
}
// Function to print the leftView
// of Binary Tree
void leftView(struct node* root)
{
// Queue to store all
// the nodes of the tree
queue<node*> q;
leftViewUtil(root, q);
}
// Driver Code
int main()
{
struct node* root = newNode(10);
root->left = newNode(12);
root->right = newNode(3);
root->left->right = newNode(4);
root->right->left = newNode(5);
root->right->left->right = newNode(6);
root->right->left->right->left = newNode(18);
root->right->left->right->right = newNode(7);
leftView(root);
return 0;
}
Java
// Java program to print the
// left view of Binary Tree
import java.util.*;
class GFG
{
// A Binary Tree Node
static class node
{
int data;
node left, right;
};
// A utility function to create a new
// Binary Tree node
static node newNode(int item)
{
node temp = new node();
temp.data = item;
temp.left = null;
temp.right = null;
return temp;
}
static Queue<node> q;
// Utility function to print the left view of
// the binary tree
static void leftViewUtil( node root )
{
if (root == null)
return;
// add root
q.add(root);
// Delimiter
q.add(null);
while (q.size() > 0)
{
node temp = q.peek();
if (temp != null)
{
// Prints first node
// of each level
System.out.print(temp.data + " ");
// add children of all nodes at
// current level
while (q.peek() != null)
{
// If left child is present
// add into queue
if (temp.left != null)
q.add(temp.left);
// If right child is present
// add into queue
if (temp.right != null)
q.add(temp.right);
// remove the current node
q.remove();
temp = q.peek();
}
// add delimiter
// for the next level
q.add(null);
}
// remove the delimiter of
// the previous level
q.remove();
}
}
// Function to print the leftView
// of Binary Tree
static void leftView( node root)
{
// Queue to store all
// the nodes of the tree
q = new LinkedList<node>();
leftViewUtil(root);
}
// Driver Code
public static void main(String args[])
{
node root = newNode(10);
root.left = newNode(12);
root.right = newNode(3);
root.left.right = newNode(4);
root.right.left = newNode(5);
root.right.left.right = newNode(6);
root.right.left.right.left = newNode(18);
root.right.left.right.right = newNode(7);
leftView(root);
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 program to print the # left view of Binary Tree # Binary Tree Node """ utility that allocates a newNode with the given key """ class newNode: # Construct to create a newNode def __init__(self, key): self.data = key self.left = None self.right = None self.hd=0 # Utility function to print the left # view of the binary tree def leftViewUtil(root, q) : if (root == None) : return # append root q.append(root) # Delimiter q.append(None) while (len(q)): temp = q[0] if (temp): # Prints first node of each level print(temp.data, end = " ") # append children of all nodes # at current level while (q[0] != None) : temp = q[0] # If left child is present # append into queue if (temp.left) : q.append(temp.left) # If right child is present # append into queue if (temp.right) : q.append(temp.right) # Pop the current node q.pop(0) # append delimiter # for the next level q.append(None) # Pop the delimiter of # the previous level q.pop(0) # Function to print the leftView # of Binary Tree def leftView(root): # Queue to store all # the nodes of the tree q = [] leftViewUtil(root, q) # Driver Code if __name__ == '__main__': root = newNode(10) root.left = newNode(12) root.right = newNode(3) root.left.right = newNode(4) root.right.left = newNode(5) root.right.left.right = newNode(6) root.right.left.right.left = newNode(18) root.right.left.right.right = newNode(7) leftView(root) # This code is contributed by # Shubham Singh(SHUBHAMSINGH10)
C#
// C# program to print the
// left view of Binary Tree
using System;
using System.Collections.Generic;
class GFG
{
// A Binary Tree Node
public class node
{
public int data;
public node left, right;
};
// A utility function to create a new
// Binary Tree node
static node newNode(int item)
{
node temp = new node();
temp.data = item;
temp.left = null;
temp.right = null;
return temp;
}
static Queue<node> q = new Queue<node>();
// Utility function to print the left view of
// the binary tree
static void leftViewUtil( node root )
{
if (root == null)
return;
// add root
q.Enqueue(root);
// Delimiter
q.Enqueue(null);
while (q.Count > 0)
{
node temp = q.Peek();
if (temp != null)
{
// Prints first node
// of each level
Console.Write(temp.data + " ");
// add children of all nodes at
// current level
while (q.Peek() != null)
{
// If left child is present
// add into queue
if (temp.left != null)
q.Enqueue(temp.left);
// If right child is present
// add into queue
if (temp.right != null)
q.Enqueue(temp.right);
// remove the current node
q.Dequeue();
temp = q.Peek();
}
// add delimiter
// for the next level
q.Enqueue(null);
}
// remove the delimiter of
// the previous level
q.Dequeue();
}
}
// Function to print the leftView
// of Binary Tree
static void leftView( node root)
{
// Queue to store all
// the nodes of the tree
q = new Queue<node>();
leftViewUtil(root);
}
// Driver Code
public static void Main(String []args)
{
node root = newNode(10);
root.left = newNode(12);
root.right = newNode(3);
root.left.right = newNode(4);
root.right.left = newNode(5);
root.right.left.right = newNode(6);
root.right.left.right.left = newNode(18);
root.right.left.right.right = newNode(7);
leftView(root);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript program to print the left view of Binary Tree
// Binary Tree Node
class node
{
constructor(item) {
this.left = null;
this.right = null;
this.data = item;
}
}
// A utility function to create a new
// Binary Tree node
function newNode(item)
{
let temp = new node(item);
return temp;
}
let q = [];
// Utility function to print the left view of
// the binary tree
function leftViewUtil(root)
{
if (root == null)
return;
// add root
q.push(root);
// Delimiter
q.push(null);
while (q.length > 0)
{
let temp = q[0];
if (temp != null)
{
// Prints first node
// of each level
document.write(temp.data + " ");
// add children of all nodes at
// current level
while (q[0] != null)
{
// If left child is present
// add into queue
if (temp.left != null)
q.push(temp.left);
// If right child is present
// add into queue
if (temp.right != null)
q.push(temp.right);
// remove the current node
q.shift();
temp = q[0];
}
// add delimiter
// for the next level
q.push(null);
}
// remove the delimiter of
// the previous level
q.shift();
}
}
// Function to print the leftView
// of Binary Tree
function leftView(root)
{
// Queue to store all
// the nodes of the tree
q = [];
leftViewUtil(root);
}
let root = newNode(10);
root.left = newNode(12);
root.right = newNode(3);
root.left.right = newNode(4);
root.right.left = newNode(5);
root.right.left.right = newNode(6);
root.right.left.right.left = newNode(18);
root.right.left.right.right = newNode(7);
leftView(root);
</script>
Salida :
10 12 4 6 18
Complejidad temporal : O(N) donde N es el número de vértices en el árbol binario.
Espacio Auxiliar : O(N).
Publicación traducida automáticamente
Artículo escrito por Sakshi_Srivastava y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA