Dado un árbol binario enraizado en el Node 1, la tarea es imprimir los elementos en el siguiente orden definido.
- Primero, imprima todos los elementos del último nivel de una manera alternativa, por ejemplo, primero imprime el elemento más a la izquierda y luego el elemento más a la derecha y continúa así hasta que todos los elementos se atraviesen en el último nivel.
- Ahora haz lo mismo con el resto de los niveles.
Ejemplos:
Input:
1
/ \
2 3
/ \ /
4 5 6
Output: 4 6 5 2 3 1
Explanation:
First print all elements of the last
level which will be printed as follows: 4 6 5
Now tree becomes
1
/ \
2 3
Now print elements as 2 3
Now the tree becomes: 1
Input:
1
/ \
2 3
Output: 2 3 1
Enfoque :
- Realice una llamada bfs y almacene todos los Nodes presentes en el nivel i en una array vectorial.
- También realice un seguimiento del nivel máximo alcanzado en una llamada bfs.
- Ahora imprima el patrón deseado comenzando desde el nivel máximo hasta 0
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation
// for the above approach
#include <bits/stdc++.h>
using namespace std;
const int sz = 1e5;
int maxLevel = 0;
// Adjacency list
// representation of the tree
vector<int> tree[sz + 1];
// Boolean array to mark all the
// vertices which are visited
bool vis[sz + 1];
// Integer array to store
// the level of each node
int level[sz + 1];
// Array of vector where ith index
// stores all the nodes at level i
vector<int> nodes[sz + 1];
// Utility function to create an
// edge between two vertices
void addEdge(int a, int b)
{
// Add a to b's list
tree[a].push_back(b);
// Add b to a's list
tree[b].push_back(a);
}
// Modified Breadth-First Function
void bfs(int node)
{
// Create a queue of {child, parent}
queue<pair<int, int> > qu;
// Push root node in the front of
// the queue and mark as visited
qu.push({ node, 0 });
nodes[0].push_back(node);
vis[node] = true;
level[1] = 0;
while (!qu.empty()) {
pair<int, int> p = qu.front();
// Dequeue a vertex from queue
qu.pop();
vis[p.first] = true;
// Get all adjacent vertices of the dequeued
// vertex s. If any adjacent has not
// been visited then enqueue it
for (int child : tree[p.first]) {
if (!vis[child]) {
qu.push({ child, p.first });
level[child] = level[p.first] + 1;
maxLevel = max(maxLevel, level[child]);
nodes[level[child]].push_back(child);
}
}
}
}
// Function to display
// the pattern
void display()
{
for (int i = maxLevel; i >= 0; i--) {
int len = nodes[i].size();
// Printing all nodes
// at given level
for (int j = 0; j < len / 2; j++) {
cout << nodes[i][j] << " " << nodes[i][len - 1 - j] << " ";
}
// If count of nodes
// at level i is odd
// print remaining node
if (len % 2 == 1) {
cout << nodes[i][len / 2] << " ";
}
}
}
// Driver code
int main()
{
// Number of vertices
int n = 6;
addEdge(1, 2);
addEdge(1, 3);
addEdge(2, 4);
addEdge(2, 5);
addEdge(3, 6);
// Calling modified bfs function
bfs(1);
display();
return 0;
}
Java
// Java implementation
// for the above approach
import java.util.*;
@SuppressWarnings("unchecked")
class GFG{
static int sz = 100000;
static int maxLevel = 0;
// Adjacency list
// representation of the tree
static ArrayList []tree = new ArrayList[sz + 1];
// boolean array to mark all the
// vertices which are visited
static boolean []vis = new boolean[sz + 1];
// Integer array to store
// the level of each node
static int []level = new int[sz + 1];
// Array of vector where ith index
// stores all the nodes at level i
static ArrayList []nodes = new ArrayList[sz + 1];
// Utility function to create an
// edge between two vertices
static void addEdge(int a, int b)
{
// Add a to b's list
tree[a].add(b);
// Add b to a's list
tree[b].add(a);
}
static class Pair
{
int Key, Value;
Pair(int Key, int Value)
{
this.Key = Key;
this.Value = Value;
}
}
// Modified Breadth-Key Function
static void bfs(int node)
{
// Create a queue of {child, parent}
Queue<Pair> qu = new LinkedList<>();
// Push root node in the front of
// the queue and mark as visited
qu.add(new Pair(node, 0));
nodes[0].add(node);
vis[node] = true;
level[1] = 0;
while (qu.size() != 0)
{
Pair p = qu.poll();
// Dequeue a vertex from queue
vis[p.Key] = true;
// Get all adjacent vertices of the dequeued
// vertex s. If any adjacent has not
// been visited then put it
for(int child : (ArrayList<Integer>)tree[p.Key])
{
if (!vis[child])
{
qu.add(new Pair(child, p.Key));
level[child] = level[p.Key] + 1;
maxLevel = Math.max(maxLevel,
level[child]);
nodes[level[child]].add(child);
}
}
}
}
// Function to display
// the pattern
static void display()
{
for(int i = maxLevel; i >= 0; i--)
{
int len = nodes[i].size();
// Printing all nodes
// at given level
for(int j = 0; j < len / 2; j++)
{
System.out.print((int)nodes[i].get(j) + " " +
(int)nodes[i].get(len - 1 - j) +
" ");
}
// If count of nodes
// at level i is odd
// print remaining node
if (len % 2 == 1)
{
System.out.print(
(int)nodes[i].get(len / 2) + " ");
}
}
}
// Driver code
public static void main(String[] args)
{
for(int i = 0; i < sz + 1; i++)
{
tree[i] = new ArrayList();
nodes[i] = new ArrayList();
vis[i] = false;
level[i] = 0;
}
addEdge(1, 2);
addEdge(1, 3);
addEdge(2, 4);
addEdge(2, 5);
addEdge(3, 6);
// Calling modified bfs function
bfs(1);
display();
}
}
// This code is contributed by pratham76
Python3
# Python3 implementation
# for the above approach
from collections import deque
sz = 10 ** 5
maxLevel = 0
# Adjacency list
# representation of the tree
tree = [[] for i in range(sz + 1)]
# Boolean array to mark all the
# vertices which are visited
vis = [False] * (sz + 1)
# Integer array to store
# the level of each node
level = [0] * (sz + 1)
# Array of vector where ith index
# stores all the nodes at level i
nodes = [[] for i in range(sz + 1)]
# Utility function to create an
# edge between two vertices
def addEdge(a, b):
global tree
# Add a to b's list
tree[a].append(b)
# Add b to a's list
tree[b].append(a)
# Modified Breadth-First Function
def bfs(node):
global maxLevel
# Create a queue of {child, parent}
qu = deque()
# Push root node in the front of
# the queue and mark as visited
qu.append([node, 0 ])
nodes[0].append(node)
vis[node] = True
level[1] = 0
while (len(qu) > 0):
p = qu.popleft()
# Dequeue a vertex from queue
# qu.pop()
vis[p[0]] = True
# Get all adjacent vertices of the dequeued
# vertex s. If any adjacent has not
# been visited then enqueue it
for child in tree[p[0]]:
if (not vis[child]):
qu.append([child, p[0]])
level[child] = level[p[0]] + 1
maxLevel = max(maxLevel, level[child])
nodes[level[child]].append(child)
# Function to display
# the pattern
def display():
for i in range(maxLevel, -1, -1):
lenn = len(nodes[i])
# Printing all nodes
# at given level
for j in range(lenn // 2):
print(nodes[i][j],
nodes[i][lenn - 1 - j], end = " ")
# If count of nodes
# at level i is odd
# print remaining node
if (lenn % 2 == 1):
print(nodes[i][lenn // 2], end = " ")
# Driver code
if __name__ == '__main__':
# Number of vertices
n = 6
addEdge(1, 2)
addEdge(1, 3)
addEdge(2, 4)
addEdge(2, 5)
addEdge(3, 6)
# Calling modified bfs function
bfs(1)
display()
# This code is contributed by mohit kumar 29
C#
// C# implementation
// for the above approach
using System;
using System.Collections.Generic;
using System.Collections;
class GFG{
static int sz = 100000;
static int maxLevel = 0;
// Adjacency list
// representation of the tree
static ArrayList []tree = new ArrayList[sz + 1];
// Boolean array to mark all the
// vertices which are visited
static bool []vis = new bool[sz + 1];
// Integer array to store
// the level of each node
static int []level = new int[sz + 1];
// Array of vector where ith index
// stores all the nodes at level i
static ArrayList []nodes = new ArrayList[sz + 1];
// Utility function to create an
// edge between two vertices
static void addEdge(int a, int b)
{
// Add a to b's list
tree[a].Add(b);
// Add b to a's list
tree[b].Add(a);
}
// Modified Breadth-First Function
static void bfs(int node)
{
// Create a queue of {child, parent}
Queue qu = new Queue();
// Push root node in the front of
// the queue and mark as visited
qu.Enqueue(new KeyValuePair<int, int>(node, 0));
nodes[0].Add(node);
vis[node] = true;
level[1] = 0;
while(qu.Count != 0)
{
KeyValuePair<int,
int> p = (KeyValuePair<int,
int>)qu.Peek();
// Dequeue a vertex from queue
qu.Dequeue();
vis[p.Key] = true;
// Get all adjacent vertices of the dequeued
// vertex s. If any adjacent has not
// been visited then enqueue it
foreach(int child in tree[p.Key])
{
if (!vis[child])
{
qu.Enqueue(new KeyValuePair<int, int>(
child, p.Key));
level[child] = level[p.Key] + 1;
maxLevel = Math.Max(maxLevel, level[child]);
nodes[level[child]].Add(child);
}
}
}
}
// Function to display
// the pattern
static void display()
{
for(int i = maxLevel; i >= 0; i--)
{
int len = nodes[i].Count;
// Printing all nodes
// at given level
for(int j = 0; j < len / 2; j++)
{
Console.Write((int)nodes[i][j] + " " +
(int)nodes[i][len - 1 - j] +
" ");
}
// If count of nodes
// at level i is odd
// print remaining node
if (len % 2 == 1)
{
Console.Write((int)nodes[i][len / 2] + " ");
}
}
}
// Driver code
public static void Main(string[] args)
{
for(int i = 0; i < sz + 1; i++)
{
tree[i] = new ArrayList();
nodes[i] = new ArrayList();
vis[i] = false;
level[i] = 0;
}
addEdge(1, 2);
addEdge(1, 3);
addEdge(2, 4);
addEdge(2, 5);
addEdge(3, 6);
// Calling modified bfs function
bfs(1);
display();
}
}
// This code is contributed by rutvik_56
Javascript
<script>
// JavaScript implementation
// for the above approach
let sz = 100000;
let maxLevel = 0;
// Adjacency list
// representation of the tree
let tree = new Array(sz + 1);
// boolean array to mark all the
// vertices which are visited
let vis = new Array(sz + 1);
// Integer array to store
// the level of each node
let level = new Array(sz + 1);
// Array of vector where ith index
// stores all the nodes at level i
let nodes = new Array(sz + 1);
// Utility function to create an
// edge between two vertices
function addEdge(a,b)
{
// Add a to b's list
tree[a].push(b);
// Add b to a's list
tree[b].push(a);
}
// Modified Breadth-Key Function
function bfs(node)
{
let qu=[];
// Push root node in the front of
// the queue and mark as visited
qu.push([node, 0]);
nodes[0].push(node);
vis[node] = true;
level[1] = 0;
while (qu.length != 0)
{
let p = qu.shift();
// Dequeue a vertex from queue
vis[p[0]] = true;
// Get all adjacent vertices of the dequeued
// vertex s. If any adjacent has not
// been visited then put it
for(let child=0;child<tree[p[0]].length;child++)
{
if (!vis[tree[p[0]][child]])
{
qu.push([tree[p[0]][child], p[0]]);
level[tree[p[0]][child]] = level[p[0]] + 1;
maxLevel = Math.max(maxLevel,
level[tree[p[0]][child]]);
nodes[level[tree[p[0]][child]]].
push(tree[p[0]][child]);
}
}
}
}
// Function to display
// the pattern
function display()
{
for(let i = maxLevel; i >= 0; i--)
{
let len = nodes[i].length;
// Printing all nodes
// at given level
for(let j = 0; j < Math.floor(len / 2); j++)
{
document.write(nodes[i][j] + " " +
nodes[i][len - 1 - j] +
" ");
}
// If count of nodes
// at level i is odd
// print remaining node
if (len % 2 == 1)
{
document.write(
nodes[i][Math.floor(len / 2)] + " ");
}
}
}
// Driver code
for(let i = 0; i < sz + 1; i++)
{
tree[i] = [];
nodes[i] = [];
vis[i] = false;
level[i] = 0;
}
addEdge(1, 2);
addEdge(1, 3);
addEdge(2, 4);
addEdge(2, 5);
addEdge(3, 6);
// Calling modified bfs function
bfs(1);
display();
// This code is contributed by patel2127
</script>
Producción:
4 6 5 2 3 1
Complejidad temporal : O(V + E), donde V es el número total de vértices y E es el número total de aristas.
Espacio Auxiliar : O(V).