Dado un árbol binario, la tarea es imprimir el orden de nivel inverso en forma de espiral.
Ejemplos:
Input:
1
/ \
2 3
/ \ / \
4 5 6 7
Output: 4 5 6 7 3 2 1
Input:
5
/ \
6 4
/ \ /
7 1 8
\ \
3 10
Output: 3 10 8 1 7 6 4 5
Enfoque: La idea es atravesar el árbol en orden de nivel inverso pero con una ligera modificación. Usaremos una bandera variable e inicialmente estableceremos su valor en uno. A medida que completamos el recorrido del árbol en orden de nivel inverso, de izquierda a derecha estableceremos el valor de la bandera en cero, de modo que la próxima vez que atravesemos el árbol de derecha a izquierda y cuando completemos el recorrido establezcamos su valor de nuevo en una. Repetiremos todo este paso hasta que hayamos recorrido el Árbol Binario por completo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to print reverse level order
// traversal of a binary tree in spiral form
#include <bits/stdc++.h>
using namespace std;
// Binary tree Node
struct Node {
struct Node* left;
struct Node* right;
int data;
Node(int data)
{
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
// Recursive Function to find height
// of binary tree
int height(struct Node* root)
{
if (root == NULL)
return 0;
// Compute the height of each subtree
int lheight = height(root->left);
int rheight = height(root->right);
// Return the maximum of two
return max(lheight + 1, rheight + 1);
}
// Function to Print Nodes from right to left
void rightToLeft(struct Node* root, int level)
{
if (root == NULL)
return;
if (level == 1)
cout << root->data << " ";
else if (level > 1) {
rightToLeft(root->right, level - 1);
rightToLeft(root->left, level - 1);
}
}
// Function to Print Nodes from left to right
void leftToRight(struct Node* root, int level)
{
if (root == NULL)
return;
if (level == 1)
cout << root->data << " ";
else if (level > 1) {
leftToRight(root->left, level - 1);
leftToRight(root->right, level - 1);
}
}
// Function to print Reverse level order traversal
// of a Binary tree in spiral form
void reverseSpiral(struct Node* root)
{
// Flag is used to mark the change
// in level
int flag = 1;
// Height of tree
int h = height(root);
for (int i = h; i >= 1; i--) {
// If flag value is one print Nodes
// from left to right
if (flag == 1) {
leftToRight(root, i);
// Mark flag as zero so that next time
// tree is traversed from right to left
flag = 0;
}
// If flag is zero print Nodes
// from right to left
else if (flag == 0) {
rightToLeft(root, i);
// Mark flag as one so that next time
// Nodes are printed from left to right
flag = 1;
}
}
}
// Driver code
int main()
{
struct Node* root = new Node(5);
root->left = new Node(9);
root->right = new Node(3);
root->left->left = new Node(6);
root->right->right = new Node(4);
root->left->left->left = new Node(8);
root->left->left->right = new Node(7);
reverseSpiral(root);
return 0;
}
Java
// Java program to print reverse level order
// traversal of a binary tree in spiral form
class Solution {
// Binary tree Node
static class Node {
Node left;
Node right;
int data;
Node(int data)
{
this.data = data;
this.left = null;
this.right = null;
}
};
// Recursive Function to find height
// of binary tree
static int height(Node root)
{
if (root == null)
return 0;
// Compute the height of each subtree
int lheight = height(root.left);
int rheight = height(root.right);
// Return the maximum of two
return Math.max(lheight + 1, rheight + 1);
}
// Function to Print Nodes from right to left
static void rightToLeft(Node root, int level)
{
if (root == null)
return;
if (level == 1)
System.out.print(root.data + " ");
else if (level > 1) {
rightToLeft(root.right, level - 1);
rightToLeft(root.left, level - 1);
}
}
// Function to Print Nodes from left to right
static void leftToRight(Node root, int level)
{
if (root == null)
return;
if (level == 1)
System.out.print(root.data + " ");
else if (level > 1) {
leftToRight(root.left, level - 1);
leftToRight(root.right, level - 1);
}
}
// Function to print Reverse level order traversal
// of a Binary tree in spiral form
static void reverseSpiral(Node root)
{
// Flag is used to mark the change
// in level
int flag = 1;
// Height of tree
int h = height(root);
for (int i = h; i >= 1; i--) {
// If flag value is one print Nodes
// from left to right
if (flag == 1) {
leftToRight(root, i);
// Mark flag as zero so that next time
// tree is traversed from right to left
flag = 0;
}
// If flag is zero print Nodes
// from right to left
else if (flag == 0) {
rightToLeft(root, i);
// Mark flag as one so that next time
// Nodes are printed from left to right
flag = 1;
}
}
}
// Driver code
public static void main(String args[])
{
Node root = new Node(5);
root.left = new Node(9);
root.right = new Node(3);
root.left.left = new Node(6);
root.right.right = new Node(4);
root.left.left.left = new Node(8);
root.left.left.right = new Node(7);
reverseSpiral(root);
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 program to print reverse level order # traversal of a binary tree in spiral form class newNode: # Construct to create a newNode def __init__(self, key): self.data = key self.left = None self.right = None # Recursive Function to find height # of binary tree def height(root): if (root == None): return 0 # Compute the height of each subtree lheight = height(root.left) rheight = height(root.right) # Return the maximum of two return max(lheight + 1, rheight + 1) # Function to Print Nodes from right to left def rightToLeft(root, level): if (root == None): return if (level == 1): print(root.data, end =" ") elif (level > 1): rightToLeft(root.right, level - 1) rightToLeft(root.left, level - 1) # Function to Print Nodes from left to right def leftToRight(root, level): if (root == None): return if (level == 1) : print(root.data, end = " ") elif (level > 1): leftToRight(root.left, level - 1) leftToRight(root.right, level - 1) # Function to print Reverse level order traversal # of a Binary tree in spiral form def reverseSpiral(root): # Flag is used to mark the # change in level flag = 1 # Height of tree h = height(root) for i in range(h, 0, -1): # If flag value is one print Nodes # from left to right if (flag == 1): leftToRight(root, i) # Mark flag as zero so that next time # tree is traversed from right to left flag = 0 # If flag is zero print Nodes # from right to left elif (flag == 0): rightToLeft(root, i) # Mark flag as one so that next time # Nodes are printed from left to right flag = 1 # Driver Code if __name__ == '__main__': root = newNode(5) root.left = newNode(9) root.right = newNode(3) root.left.left = newNode(6) root.right.right = newNode(4) root.left.left.left = newNode(8) root.left.left.right = newNode(7) reverseSpiral(root) # This code is contributed # by SHUBHAMSINGH10
C#
// C# program to print reverse level order
// traversal of a binary tree in spiral form
using System;
class GFG {
// Binary tree Node
public class Node {
public Node left;
public Node right;
public int data;
public Node(int data)
{
this.data = data;
this.left = null;
this.right = null;
}
};
// Recursive Function to find height
// of binary tree
static int height(Node root)
{
if (root == null)
return 0;
// Compute the height of each subtree
int lheight = height(root.left);
int rheight = height(root.right);
// Return the maximum of two
return Math.Max(lheight + 1, rheight + 1);
}
// Function to Print Nodes from right to left
static void rightToLeft(Node root, int level)
{
if (root == null)
return;
if (level == 1)
Console.Write(root.data + " ");
else if (level > 1) {
rightToLeft(root.right, level - 1);
rightToLeft(root.left, level - 1);
}
}
// Function to Print Nodes from left to right
static void leftToRight(Node root, int level)
{
if (root == null)
return;
if (level == 1)
Console.Write(root.data + " ");
else if (level > 1) {
leftToRight(root.left, level - 1);
leftToRight(root.right, level - 1);
}
}
// Function to print Reverse level order traversal
// of a Binary tree in spiral form
static void reverseSpiral(Node root)
{
// Flag is used to mark the change
// in level
int flag = 1;
// Height of tree
int h = height(root);
for (int i = h; i >= 1; i--) {
// If flag value is one print Nodes
// from left to right
if (flag == 1) {
leftToRight(root, i);
// Mark flag as zero so that next time
// tree is traversed from right to left
flag = 0;
}
// If flag is zero print Nodes
// from right to left
else if (flag == 0) {
rightToLeft(root, i);
// Mark flag as one so that next time
// Nodes are printed from left to right
flag = 1;
}
}
}
// Driver code
public static void Main(String[] args)
{
Node root = new Node(5);
root.left = new Node(9);
root.right = new Node(3);
root.left.left = new Node(6);
root.right.right = new Node(4);
root.left.left.left = new Node(8);
root.left.left.right = new Node(7);
reverseSpiral(root);
}
}
/* This code is contributed by PrinciRaj1992 */
Javascript
<script>
// Javascript program to print reverse level order
// traversal of a binary tree in spiral form
// Binary tree Node
class Node
{
constructor(data)
{
this.data = data;
this.left = null;
this.right = null;
}
}
// Recursive Function to find height
// of binary tree
function height(root)
{
if (root == null)
return 0;
// Compute the height of each subtree
let lheight = height(root.left);
let rheight = height(root.right);
// Return the maximum of two
return Math.max(lheight + 1, rheight + 1);
}
// Function to Print Nodes from right to left
function rightToLeft(root, level)
{
if (root == null)
return;
if (level == 1)
document.write(root.data + " ");
else if (level > 1)
{
rightToLeft(root.right, level - 1);
rightToLeft(root.left, level - 1);
}
}
// Function to Print Nodes from left to right
function leftToRight(root, level)
{
if (root == null)
return;
if (level == 1)
document.write(root.data + " ");
else if (level > 1)
{
leftToRight(root.left, level - 1);
leftToRight(root.right, level - 1);
}
}
// Function to print Reverse level order traversal
// of a Binary tree in spiral form
function reverseSpiral(root)
{
// Flag is used to mark the change
// in level
let flag = 1;
// Height of tree
let h = height(root);
for(let i = h; i >= 1; i--)
{
// If flag value is one print Nodes
// from left to right
if (flag == 1)
{
leftToRight(root, i);
// Mark flag as zero so that next time
// tree is traversed from right to left
flag = 0;
}
// If flag is zero print Nodes
// from right to left
else if (flag == 0)
{
rightToLeft(root, i);
// Mark flag as one so that next time
// Nodes are printed from left to right
flag = 1;
}
}
}
// Driver code
let root = new Node(5);
root.left = new Node(9);
root.right = new Node(3);
root.left.left = new Node(6);
root.right.right = new Node(4);
root.left.left.left = new Node(8);
root.left.left.right = new Node(7);
reverseSpiral(root);
// This code is contributed by unknown2108
</script>
Producción:
8 7 4 6 9 3 5
Análisis de Complejidad de Tiempo : La mejor complejidad de tiempo de caso de reverseSpiral() es O(n+n/2+n/4…) = O(n) en el caso de un árbol binario perfecto. Y la complejidad temporal del peor de los casos es O(n 2 ) [O((n)+(n-1)+(n-2)+…] en caso de que se tome como entrada un árbol sesgado.
Espacio auxiliar : O (n) para la pila de llamadas desde que se usa la recursividad.
Implementación iterativa:
el problema anterior se puede resolver con la ayuda de la cola y la pila. Simplemente realice un recorrido en espiral normal, use la pila para usar los elementos inversos alternativamente. A continuación se muestra la implementación de la misma –
C++14
#include <bits/stdc++.h>
using namespace std;
// Node structure
struct Node {
int data;
Node* left;
Node* right;
Node(int val)
{
data = val;
left = right = NULL;
}
};
// function to perform
// reversal spiral traversal
void reverseSpiral(Node* root)
{
if (root == NULL) {
return;
}
queue<Node*> q;
stack<int> s;
bool reverse = true;
q.push(root);
// iterate until queue is empty
while (!q.empty()) {
// calculate size of level
int count = q.size();
// iterate over level nodes
for (int i = 0; i < count; i++) {
Node* curr = q.front();
q.pop();
s.push(curr->data);
if (reverse) {
if (curr->right) {
q.push(curr->right);
}
if (curr->left) {
q.push(curr->left);
}
}
else {
if (curr->left) {
q.push(curr->left);
}
if (curr->right) {
q.push(curr->right);
}
}
}
reverse = !reverse;
}
// pop and print reversed nodes
while (!s.empty()) {
int curr = s.top();
cout << curr << " ";
s.pop();
}
}
// Driver code
int main()
{
Node* root = new Node(5);
root->left = new Node(9);
root->right = new Node(3);
root->left->left = new Node(6);
root->left->right = new Node(4);
root->left->left->left = new Node(8);
root->left->left->right = new Node(7);
reverseSpiral(root);
return 0;
}
Python3
from collections import deque # Node structure class Node: def __init__(self, x): self.data = x self.right = None self.left = None # function to perform # reversal spiral traversal def reverseSpiral(root): if (root == None): return q = deque() s = [] reverse = True q.append(root) # iterate until queue is empty while (len(q) > 0): # calculate size of level count = len(q) # iterate over level nodes for i in range(count): curr = q.popleft() s.append(curr.data) if (reverse): if (curr.right): q.append(curr.right) if (curr.left): q.append(curr.left) else: if (curr.left): q.append(curr.left) if (curr.right): q.append(curr.right) reverse = not reverse # pop and print reversed nodes while (len(s) > 0): curr = s[-1] print(curr, end = " ") del s[-1] # Driver code if __name__ == '__main__': root = Node(5) root.left = Node(9) root.right = Node(3) root.left.left = Node(6) root.left.right = Node(4) root.left.left.left = Node(8) root.left.left.right = Node(7) reverseSpiral(root) # This code is contributed by mohit kumar 29.
Javascript
<script>
class Node
{
constructor(data)
{
this.data = data;
this.left = this.right = null;
}
}
// function to perform
// reversal spiral traversal
function reverseSpiral(root)
{
if (root == null)
return
let q = [];
let s = [];
let reverse = true;
q.push(root)
while ((q).length > 0)
{
// calculate size of level
let count = (q).length;
// iterate over level nodes
for (let i = 0; i < (count); i++)
{
curr = q.shift();
s.push(curr.data);
if (reverse)
{
if (curr.right)
q.push(curr.right);
if (curr.left)
q.push(curr.left);
}
else
{
if (curr.left)
q.push(curr.left);
if (curr.right)
q.push(curr.right);
}
}
reverse = !reverse
}
// pop and prreversed nodes
while ((s).length > 0)
{
curr = s.pop();
document.write(curr+" ");
}
}
// Driver code
let root = new Node(5)
root.left = new Node(9)
root.right = new Node(3)
root.left.left = new Node(6)
root.left.right = new Node(4)
root.left.left.left = new Node(8)
root.left.left.right = new Node(7)
reverseSpiral(root)
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
8 7 4 6 9 3 5
Complejidad temporal : O(N)
Espacio auxiliar: O(N)
Mejorado por: HarendraSingh22
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