Dado un árbol binario. La tarea es imprimir el recorrido circular en espiral inversa en el sentido de las agujas del reloj del árbol binario dado.
El recorrido inverso en el sentido de las agujas del reloj significa atravesar el árbol en el sentido de las agujas del reloj en espiral, comenzando desde la parte inferior en lugar del Node raíz superior.
Ejemplos:
Input :
1
/ \
2 3
/ \ \
4 5 6
/ / \
7 8 9
Output : 9 8 7 1 6 5 4 2 3
Input :
20
/ \
8 22
/ \ / \
5 3 4 25
/ \
10 14
Output : 14 10 20 25 4 3 5 8 22
Enfoque: La idea es usar dos variables i inicializadas a 1 y j inicializadas a la altura del árbol y ejecutar un ciclo while que no se interrumpa hasta que i sea mayor que j .
- Use otra bandera variable e inicialícela a 0. Ahora, en el ciclo while, verifique una condición de que si la bandera es igual a 0, entonces atraviese el árbol de derecha a izquierda y marque la bandera como 1 para que la próxima vez atraviese el árbol de izquierda a derecha, esto se hace para mantener el orden de recorrido en espiral en el sentido de las agujas del reloj.
- Luego disminuya el valor de j para que la próxima vez se visite el nivel justo por encima del nivel actual.
- Además, cuando atravesemos el nivel desde arriba, marcaremos la bandera como 0 para que la próxima vez atravesemos el árbol de derecha a izquierda y luego incrementemos el valor de i para que la próxima vez visitemos el nivel justo debajo del nivel actual.
- Repita todo el proceso hasta que el árbol binario esté completamente recorrido.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#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)
{
// Base condition
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(1 + lheight, 1 + rheight);
}
// 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 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 reverse clockwise spiral
// traversal of a binary tree
void ReverseClockWiseSpiral(struct Node* root)
{
int i = 1;
int j = height(root);
// Flag to mark a change in the direction
// of printing nodes
int flag = 0;
while (i <= j) {
// If flag is zero print nodes
// from right to left
if (flag == 0) {
rightToLeft(root, j);
// Set the value of flag as zero
// so that nodes are next time
// printed from left to right
flag = 1;
// Decrement j
j--;
}
// If flag is one print nodes
// from left to right
else {
leftToRight(root, i);
// Set the value of flag as zero
// so that nodes are next time
// printed from right to left
flag = 0;
// Increment i
i++;
}
}
}
// Driver code
int main()
{
struct Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->right->left = new Node(6);
root->right->right = new Node(7);
root->left->right = new Node(5);
ReverseClockWiseSpiral(root);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
// 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)
{
// Base condition
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(1 + lheight, 1 + rheight);
}
// 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 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 reverse clockwise spiral
// traversal of a binary tree
static void ReverseClockWiseSpiral( Node root)
{
int i = 1;
int j = height(root);
// Flag to mark a change in the direction
// of printing nodes
int flag = 0;
while (i <= j)
{
// If flag is zero print nodes
// from right to left
if (flag == 0)
{
rightToLeft(root, j);
// Set the value of flag as zero
// so that nodes are next time
// printed from left to right
flag = 1;
// Decrement j
j--;
}
// If flag is one print nodes
// from left to right
else
{
leftToRight(root, i);
// Set the value of flag as zero
// so that nodes are next time
// printed from right to left
flag = 0;
// Increment i
i++;
}
}
}
// 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.right.left = new Node(6);
root.right.right = new Node(7);
root.left.right = new Node(5);
ReverseClockWiseSpiral(root);
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 implementation of the approach # Binary tree node class Node: def __init__(self,data): self.left = None self.right = None self.data = data; # Recursive Function to find height # of binary tree def height(root): # Base condition 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(1 + lheight, 1 + rheight); # 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 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 Reverse clockwise # spiral traversal of a binary tree def ReverseClockWiseSpiral(root): i = 1; j = height(root); # Flag to mark a change in the # direction of printing nodes flag = 0; while (i <= j): # If flag is zero print nodes # from right to left if (flag == 0): rightToLeft(root, j); # Set the value of flag as zero # so that nodes are next time # printed from left to right flag = 1; # Increment i j -= 1; # If flag is one print nodes # from left to right else: leftToRight(root, i); # Set the value of flag as zero # so that nodes are next time # printed from right to left flag = 0; # Decrement j i += 1; # Driver code if __name__=="__main__": root = Node(1); root.left = Node(2); root.right = Node(3); root.left.left = Node(4); root.right.left = Node(6); root.right.right = Node(7); root.left.right = Node(5); ReverseClockWiseSpiral(root); # This code is contributed by rutvik_56
C#
// C# implementation of the approach
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)
{
// Base condition
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(1 + lheight, 1 + rheight);
}
// 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 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 reverse clockwise spiral
// traversal of a binary tree
static void ReverseClockWiseSpiral( Node root)
{
int i = 1;
int j = height(root);
// Flag to mark a change in the direction
// of printing nodes
int flag = 0;
while (i <= j)
{
// If flag is zero print nodes
// from right to left
if (flag == 0)
{
rightToLeft(root, j);
// Set the value of flag as zero
// so that nodes are next time
// printed from left to right
flag = 1;
// Decrement j
j--;
}
// If flag is one print nodes
// from left to right
else
{
leftToRight(root, i);
// Set the value of flag as zero
// so that nodes are next time
// printed from right to left
flag = 0;
// Increment i
i++;
}
}
}
// 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.right.left = new Node(6);
root.right.right = new Node(7);
root.left.right = new Node(5);
ReverseClockWiseSpiral(root);
}
}
// This code contributed by Rajput-Ji
Javascript
<script>
// JavaScript implementation of the approach
// Binary tree node
class Node
{
constructor(data) {
this.left = null;
this.right = null;
this.data = data;
}
}
// Recursive Function to find height
// of binary tree
function height(root)
{
// Base condition
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(1 + lheight, 1 + rheight);
}
// 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 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 reverse clockwise spiral
// traversal of a binary tree
function ReverseClockWiseSpiral(root)
{
let i = 1;
let j = height(root);
// Flag to mark a change in the direction
// of printing nodes
let flag = 0;
while (i <= j)
{
// If flag is zero print nodes
// from right to left
if (flag == 0)
{
rightToLeft(root, j);
// Set the value of flag as zero
// so that nodes are next time
// printed from left to right
flag = 1;
// Decrement j
j--;
}
// If flag is one print nodes
// from left to right
else
{
leftToRight(root, i);
// Set the value of flag as zero
// so that nodes are next time
// printed from right to left
flag = 0;
// Increment i
i++;
}
}
}
let root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.right.left = new Node(6);
root.right.right = new Node(7);
root.left.right = new Node(5);
ReverseClockWiseSpiral(root);
</script>
Producción:
7 6 5 4 1 3 2
Complejidad de tiempo : O(N^2), donde N es el número total de Nodes 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