Dado un árbol binario y un entero K , la tarea es imprimir el recorrido del orden de niveles de tal manera que los primeros K niveles se impriman de izquierda a derecha, los siguientes K niveles se impriman de derecha a izquierda y luego los siguientes K niveles se impriman de izquierda a derecha. a la derecha y así sucesivamente.
Ejemplos :
Entrada: K = 1
1
/ \
2 3
/ \ /
4 9 8
Salida:
1
3 2
4 9 8
Explicación: En el ejemplo anterior, el primer nivel se imprime de izquierda a derecha
y el segundo nivel se imprime de derecha a izquierda, y luego el último nivel se
imprime de izquierda a derecha.Entrada: K = 3
1
/ \
2 3
/ \ / \
4 5 6 7
/ \ / \ /
8 9 10 11 12
/ \ /
13 14 15Salida:
1
2 3
4 5 6 7
12 11 10 9 8
15 14 13
Explicación: En el ejemplo anterior, los primeros 3 niveles se imprimen de izquierda a derecha
y los últimos 2 niveles se imprimen de derecha a izquierda.
Planteamiento: La solución al problema se basa en la siguiente idea:
Comience a realizar un recorrido de orden de niveles en el árbol desde el extremo izquierdo. Después de cada nivel K, cambie la dirección de impresión de los elementos.
Para este uso pila. Cuando los niveles se impriman desde la derecha, mantenga esos valores en la pila e imprima los elementos de la pila uno por uno desde arriba. Debido a la propiedad last in first out de la pila, los elementos se imprimirían en orden inverso.
Siga los pasos mencionados a continuación para implementar la idea anterior:
- Utilice la cola para realizar el cruce de orden de niveles .
- En cada nivel:
- Si se va a imprimir desde la izquierda, imprímalos y empuje sus Nodes secundarios en la cola.
- Si este nivel se va a imprimir desde el lado derecho, empuje los elementos en una pila e imprímalos después de recorrer todo el nivel.
- Si los niveles K están cubiertos, cambie la dirección de impresión a partir de la siguiente.
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;
// Binary Tree node
struct Node {
int data;
Node *left, *right;
};
// Function that returns a new node
Node* newNode(int data)
{
Node* temp = new Node();
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
// Function to print the level order of tree
// by reversing the direction of traversal
// after every n levels
void traverse(Node* root, int n)
{
// NULL check
if (!root)
return;
// Queue for level order traversal
queue<Node*> q;
// Stack for
// reverse level order traversal
stack<Node*> s;
// For changing the direction
// of traversal
bool right2left = false;
// To count number of levels
int count = 0;
q.push(root);
while (!q.empty()) {
int size = q.size();
count++;
while (size--) {
root = q.front();
q.pop();
// Prints the nodes from
// left to right
if (right2left == false)
cout << root->data << " ";
// Push the nodes into stack
// for printing from right to left
else
s.push(root);
if (root->left)
q.push(root->left);
if (root->right)
q.push(root->right);
}
// If the condition satisfies
// prints the nodes from right to left.
if (right2left == true) {
while (!s.empty()) {
cout << s.top()->data << " ";
s.pop();
}
}
// If the count becomes n
// then reverse the direction
if (count == n) {
right2left = !right2left;
// Update the count to 0
count = 0;
}
cout << endl;
}
}
int main()
{
// Create a Binary Tree
Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right->left = newNode(6);
root->right->right = newNode(7);
root->left->left->left = newNode(8);
root->left->left->right = newNode(9);
root->left->right->left = newNode(10);
root->right->left->right = newNode(11);
root->right->right->left = newNode(12);
root->left->left->right->left
= newNode(13);
root->left->left->right->right
= newNode(14);
root->right->left->right->left
= newNode(15);
// Specify K to change the direction
// after every K levels.
int K = 3;
traverse(root, K);
return 0;
}
Java
import java.util.*;
import java.io.*;
// Java program for the above approach
class GFG{
// Binary Tree node
static class Node{
int data;
Node left, right;
Node(int data){
this.data = data;
left = null;
right = null;
}
}
// Function to print the level order of tree
// by reversing the direction of traversal
// after every n levels.
public static void traverse(Node root, int n){
// Null check
if(root == null){
return;
}
// Queue for level order traversal
Queue<Node> q = new ArrayDeque<Node>();
// Stack for
// reverse level order traversal
Stack<Node> s = new Stack<Node>();
// For changing the directin of traversal
Boolean right2left = false;
// To count number of levels
int count = 0;
q.add(root);
while(!q.isEmpty()){
int size = q.size();
count++;
while(size > 0){
size--;
root = q.peek();
q.remove();
// Prints the nodes from left to right
if(right2left == false){
System.out.print(root.data + " ");
}
// Push the nodes into stack
// for printing from right to left
else{
s.push(root);
}
if(root.left != null){
q.add(root.left);
}
if(root.right != null){
q.add(root.right);
}
}
// If the condition satisfies
// prints the nodes from right to left.
if(right2left == true){
while(!s.isEmpty()){
Node topElement = s.pop();
System.out.print(topElement.data + " ");
}
}
// If the count becomes n
// then reverse the direction
if(count == n){
right2left = !right2left;
// Update the count to 0
count = 0;
}
System.out.println("");
}
}
// Driver code
public static void main(String args[])
{
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);
root.left.left.left = new Node(8);
root.left.left.right = new Node(9);
root.left.right.left = new Node(10);
root.right.left.right = new Node(11);
root.right.right.left = new Node(12);
root.left.left.right.left = new Node(13);
root.left.left.right.right = new Node(14);
root.right.left.right.left = new Node(15);
// Specify K to change the direction
// after every K levels.
int K = 3;
traverse(root, K);
}
}
// This code is contributed by subhamgoyal2014.
Python3
# Python code for the above approach
# Binary Tree node
class Node:
def __init__(self, d):
self.data = d
self.left = None
self.right = None
# Function to print the level order of tree
# by reversing the direction of traversal
# after every n levels
def traverse(root, n):
# NULL check
if (root == None):
return
# Queue for level order traversal
q = []
# Stack for
# reverse level order traversal
s =[]
# For changing the direction
# of traversal
right2left = False
# To count number of levels
count = 0
q.append(root)
while(len(q) != 0):
size = len(q)
count += 1
while (size > 0):
root = q[0]
q = q[1:]
# Prints the nodes from
# left to right
if (right2left == False):
print(root.data, end = " ")
# Push the nodes into stack
# for printing from right to left
else:
s.append(root)
if (root.left):
q.append(root.left)
if (root.right):
q.append(root.right)
size -= 1
# If the condition satisfies
# prints the nodes from right to left.
if (right2left == True):
while (len(s) > 0):
print(s[-1].data,end = " ")
s.pop()
# If the count becomes n
# then reverse the direction
if (count == n):
right2left = not right2left
# Update the count to 0
count = 0
print("")
# Create a Binary Tree
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
root.left.left.left = Node(8)
root.left.left.right = Node(9)
root.left.right.left = Node(10)
root.right.left.right = Node(11)
root.right.right.left = Node(12)
root.left.left.right.left = Node(13)
root.left.left.right.right = Node(14)
root.right.left.right.left = Node(15)
# Specify K to change the direction
# after every K levels.
K = 3
traverse(root, K)
# This code is contributed by shinjanpatra
Javascript
<script>
// JavaScript code for the above approach
// Binary Tree node
class Node {
constructor(d)
{
this.data = d;
this.left = null;
this.right = null;
}
};
// Function to print the level order of tree
// by reversing the direction of traversal
// after every n levels
function traverse(root, n)
{
// NULL check
if (root==null)
return;
// Queue for level order traversal
let q = [];
// Stack for
// reverse level order traversal
let s =[];
// For changing the direction
// of traversal
let right2left = false;
// To count number of levels
let count = 0;
q.push(root);
while (q.length!=0) {
let size = q.length;
count++;
while (size--) {
root = q[0];
q.shift(root);
// Prints the nodes from
// left to right
if (right2left == false)
document.write(root.data + " ")
// Push the nodes into stack
// for printing from right to left
else
s.push(root);
if (root.left)
q.push(root.left);
if (root.right)
q.push(root.right);
}
// If the condition satisfies
// prints the nodes from right to left.
if (right2left == true) {
while (s.length!=0) {
document.write(s[s.length-1].data + " ")
s.pop();
}
}
// If the count becomes n
// then reverse the direction
if (count == n) {
right2left = !right2left;
// Update the count to 0
count = 0;
}
document.write('<br>')
}
}
// Create a Binary Tree
let root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
root.right.right = new Node(7);
root.left.left.left = new Node(8);
root.left.left.right = new Node(9);
root.left.right.left = new Node(10);
root.right.left.right = new Node(11);
root.right.right.left = new Node(12);
root.left.left.right.left
= new Node(13);
root.left.left.right.right
= new Node(14);
root.right.left.right.left
= new Node(15);
// Specify K to change the direction
// after every K levels.
let K = 3;
traverse(root, K);
// This code is contributed by Potta Lokesh
</script>
Producción
1 2 3 4 5 6 7 12 11 10 9 8 15 14 13
Complejidad de tiempo: O(N) donde N es el número de Nodes
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por upendra200223 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA