Dado un árbol genérico que consta de N Nodes, la tarea es encontrar el recorrido de orden de niveles en zigzag del árbol dado.
Ejemplos:
Aporte:
Salida:
1
3 2
4 5 6 7 8
Enfoque: El problema dado se puede resolver usando BFS Traversal . El enfoque es muy similar al de Level Order Traversal of the N-ary Tree . Se puede observar que al invertir el orden de los niveles pares durante el Level Order Traversal, la secuencia obtenida es un ZigZag traversal. Con base en estas observaciones, a continuación se detallan los pasos a seguir:
- Durante el BFS Traversal, almacene los Nodes de cada nivel en un vector , digamos curLevel[] .
- Para cada nivel respectivo, almacene curLevel en un vector de vectores , diga result[] .
- Invierta los vectores presentes en posiciones pares en result[] .
- Después de completar los pasos anteriores, todos los vectores almacenados en el resultado [] el resultado requerido.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Structure of a tree node
struct Node {
int val;
vector<Node*> child;
};
// Function to create a new node
Node* newNode(int key)
{
Node* temp = new Node;
temp->val = key;
return temp;
}
// Function to perform zig zag traversal
// of the given tree
void zigzagLevelOrder(Node* root)
{
if (root == NULL)
return;
// Stores the vectors containing nodes
// in each level of tree respectively
vector<vector<int> > result;
// Create a queue for BFS
queue<Node*> q;
// Enqueue Root of the tree
q.push(root);
// Standard Level Order Traversal
// code using queue
while (!q.empty()) {
int size = q.size();
// Stores the element in the
// current level
vector<int> curLevel;
// Iterate over all nodes of
// the current level
for (int i = 0; i < size; i++) {
Node* node = q.front();
q.pop();
curLevel.push_back(node->val);
// Insert all children of the
// current node into the queue
for (int j = 0;
j < node->child.size(); j++) {
q.push(node->child[j]);
}
}
// Insert curLevel into result
result.push_back(curLevel);
}
// Loop to Print the ZigZag Level order
// Traversal of the given tree
for (int i = 0; i < result.size(); i++) {
// If i+1 is even reverse the order
// of nodes in the current level
if ((i + 1) % 2 == 0) {
reverse(result[i].begin(),
result[i].end());
}
// Print the node of ith level
for (int j = 0;
j < result[i].size(); j++) {
cout << result[i][j] << " ";
}
cout << endl;
}
}
// 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[0]->child).push_back(newNode(5));
(root->child[1]->child).push_back(newNode(6));
(root->child[1])->child.push_back(newNode(7));
(root->child[1]->child).push_back(newNode(8));
// Function Call
zigzagLevelOrder(root);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
public class Main
{
// Class containing left and
// right child of current
// node and key value
static class Node {
public int val;
public Vector<Node> child;
public Node(int key)
{
val = key;
child = new Vector<Node>();
}
}
// Function to create a new node
static Node newNode(int key)
{
Node temp = new Node(key);
return temp;
}
// Function to perform zig zag traversal
// of the given tree
static void zigzagLevelOrder(Node root)
{
if (root == null)
return;
// Stores the vectors containing nodes
// in each level of tree respectively
Vector<Vector<Integer>> result = new Vector<Vector<Integer>>();
// Create a queue for BFS
Vector<Node> q = new Vector<Node>();
// Enqueue Root of the tree
q.add(root);
// Standard Level Order Traversal
// code using queue
while(q.size() > 0)
{
int size = q.size();
// Stores the element in the
// current level
Vector<Integer> curLevel = new Vector<Integer>();
// Iterate over all nodes of
// the current level
for(int i = 0; i < size; i++)
{
Node node = q.get(0);
q.remove(0);
curLevel.add(node.val);
// Insert all children of the
// current node into the queue
for(int j = 0; j < (node.child).size(); j++)
q.add(node.child.get(j));
}
// Insert curLevel into result
result.add(curLevel);
}
// Loop to Print the ZigZag Level order
// Traversal of the given tree
for(int i = 0; i < result.size(); i++)
{
// If i+1 is even reverse the order
// of nodes in the current level
if ((i + 1) % 2 == 0)
{
Collections.reverse(result.get(i));
}
// Print the node of ith level
for(int j = 0; j < result.get(i).size(); j++)
System.out.print(result.get(i).get(j) + " ");
System.out.println();
}
}
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(0).child).add(newNode(5));
(root.child.get(1).child).add(newNode(6));
(root.child.get(1)).child.add(newNode(7));
(root.child.get(1).child).add(newNode(8));
// Function Call
zigzagLevelOrder(root);
}
}
// This code is contributed by divyesh072019.
Python3
# Python3 program for the above approach # Structure of a tree node class Node: def __init__(self, key): self.val = key self.child = [] # Function to create a new node def newNode(key): temp = Node(key) return temp # Function to perform zig zag traversal # of the given tree def zigzagLevelOrder(root): if (root == None): return # Stores the vectors containing nodes # in each level of tree respectively result = [] # Create a queue for BFS q = [] # Enqueue Root of the tree q.append(root) # Standard Level Order Traversal # code using queue while len(q) > 0: size = len(q) # Stores the element in the # current level curLevel = [] # Iterate over all nodes of # the current level for i in range(size): node = q[0] q.pop(0) curLevel.append(node.val) # Insert all children of the # current node into the queue for j in range(len(node.child)): q.append(node.child[j]) # Insert curLevel into result result.append(curLevel) # Loop to Print the ZigZag Level order # Traversal of the given tree for i in range(len(result)): # If i+1 is even reverse the order # of nodes in the current level if ((i + 1) % 2 == 0): result[i].reverse() # Print the node of ith level for j in range(len(result[i])): print(result[i][j], end = " ") print() root = newNode(1) (root.child).append(newNode(2)) (root.child).append(newNode(3)) (root.child[0].child).append(newNode(4)) (root.child[0].child).append(newNode(5)) (root.child[1].child).append(newNode(6)) (root.child[1]).child.append(newNode(7)) (root.child[1].child).append(newNode(8)) # Function Call zigzagLevelOrder(root) # This code is contributed by decode2207.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG {
// Structure of a tree node
class Node {
public int val;
public List<Node> child;
public Node(int key)
{
val = key;
child = new List<Node>();
}
}
// Function to create a new node
static Node newNode(int key)
{
Node temp = new Node(key);
return temp;
}
// Function to perform zig zag traversal
// of the given tree
static void zigzagLevelOrder(Node root)
{
if (root == null)
return;
// Stores the vectors containing nodes
// in each level of tree respectively
List<List<int>> result = new List<List<int>>();
// Create a queue for BFS
List<Node> q = new List<Node>();
// Enqueue Root of the tree
q.Add(root);
// Standard Level Order Traversal
// code using queue
while(q.Count > 0)
{
int size = q.Count;
// Stores the element in the
// current level
List<int> curLevel = new List<int>();
// Iterate over all nodes of
// the current level
for(int i = 0; i < size; i++)
{
Node node = q[0];
q.RemoveAt(0);
curLevel.Add(node.val);
// Insert all children of the
// current node into the queue
for(int j = 0; j < (node.child).Count; j++)
q.Add(node.child[j]);
}
// Insert curLevel into result
result.Add(curLevel);
}
// Loop to Print the ZigZag Level order
// Traversal of the given tree
for(int i = 0; i < result.Count; i++)
{
// If i+1 is even reverse the order
// of nodes in the current level
if ((i + 1) % 2 == 0)
{
result[i].Reverse();
}
// Print the node of ith level
for(int j = 0; j < result[i].Count; j++)
Console.Write(result[i][j] + " ");
Console.WriteLine();
}
}
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[0].child).Add(newNode(5));
(root.child[1].child).Add(newNode(6));
(root.child[1]).child.Add(newNode(7));
(root.child[1].child).Add(newNode(8));
// Function Call
zigzagLevelOrder(root);
}
}
// This code is contributed by suresh07.
Javascript
<script>
// Javascript program for the above approach
// Structure of a tree node
class Node
{
constructor(key) {
this.child = [];
this.val = key;
}
}
// Function to create a new node
function newNode(key)
{
let temp = new Node(key);
return temp;
}
// Function to perform zig zag traversal
// of the given tree
function zigzagLevelOrder(root)
{
if (root == null)
return;
// Stores the vectors containing nodes
// in each level of tree respectively
let result = [];
// Create a queue for BFS
let q = [];
// Enqueue Root of the tree
q.push(root);
// Standard Level Order Traversal
// code using queue
while(q.length > 0)
{
let size = q.length;
// Stores the element in the
// current level
let curLevel = [];
// Iterate over all nodes of
// the current level
for(let i = 0; i < size; i++)
{
let node = q[0];
q.shift();
curLevel.push(node.val);
// Insert all children of the
// current node into the queue
for(let j = 0; j < (node.child).length; j++)
q.push(node.child[j]);
}
// Insert curLevel into result
result.push(curLevel);
}
// Loop to Print the ZigZag Level order
// Traversal of the given tree
for(let i = 0; i < result.length; i++)
{
// If i+1 is even reverse the order
// of nodes in the current level
if ((i + 1) % 2 == 0)
{
result[i].reverse();
}
// Print the node of ith level
for(let j = 0; j < result[i].length; j++)
document.write(result[i][j] + " ");
document.write("</br>");
}
}
let root = newNode(1);
(root.child).push(newNode(2));
(root.child).push(newNode(3));
(root.child[0].child).push(newNode(4));
(root.child[0].child).push(newNode(5));
(root.child[1].child).push(newNode(6));
(root.child[1]).child.push(newNode(7));
(root.child[1].child).push(newNode(8));
// Function Call
zigzagLevelOrder(root);
// This code is contributed by divyeshrabadiya07.
</script>
Producción:
1 3 2 4 5 6 7 8
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por sohailahmed46khan786 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA