Dado un árbol binario, la tarea es imprimir los Nodes del árbol en forma de espiral inversa en sentido antihorario.
Ejemplos:
Input :
1
/ \
2 3
/ \ \
4 5 6
/ / \
7 8 9
Output : 7 8 9 1 4 5 6 3 2
Input :
20
/ \
8 22
/ \ / \
5 3 4 25
/ \
10 14
Output : 10 14 20 5 3 4 25 22 8
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 interrumpirá hasta que i sea mayor que j. Usaremos otra bandera variable y la inicializaremos a 1. Ahora, en el ciclo while, verificaremos una condición de que si la bandera es igual a 1, recorreremos el árbol de izquierda a derecha y marcaremos la bandera como 0 para que la próxima vez que atravesemos la árbol de derecha a izquierda y luego disminuya el valor de j para que la próxima vez visitemos el nivel justo por encima del nivel actual. Además, cuando atravesemos el nivel desde arriba, marcaremos la banderacomo 1 para que la próxima vez atravesemos el árbol de izquierda a derecha 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 anti clockwise spiral
// traversal of a binary tree
void ReverseAntiClockWiseSpiral(struct Node* root)
{
int i = 1;
int j = height(root);
// Flag to mark a change in the direction
// of printing nodes
int flag = 1;
while (i <= j) {
// If flag is zero print nodes
// from right to left
if (flag == 0) {
rightToLeft(root, i);
// Set the value of flag as zero
// so that nodes are next time
// printed from left to right
flag = 1;
// Increment i
i++;
}
// If flag is one print nodes
// from left to right
else {
leftToRight(root, j);
// Set the value of flag as zero
// so that nodes are next time
// printed from right to left
flag = 0;
// Decrement j
j--;
}
}
}
// Driver code
int main()
{
struct Node* root = new Node(20);
root->left = new Node(8);
root->right = new Node(22);
root->left->left = new Node(5);
root->left->right = new Node(3);
root->right->left = new Node(4);
root->right->right = new Node(25);
root->left->right->left = new Node(10);
root->left->right->right = new Node(14);
ReverseAntiClockWiseSpiral(root);
return 0;
}
Java
// Java implementation of the approach
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 anti clockwise spiral
// traversal of a binary tree
static void ReverseAntiClockWiseSpiral(Node root)
{
int i = 1;
int j = height(root);
// Flag to mark a change in the direction
// of printing nodes
int flag = 1;
while (i <= j)
{
// If flag is zero print nodes
// from right to left
if (flag == 0)
{
rightToLeft(root, i);
// Set the value of flag as zero
// so that nodes are next time
// printed from left to right
flag = 1;
// Increment i
i++;
}
// If flag is one print nodes
// from left to right
else
{
leftToRight(root, j);
// Set the value of flag as zero
// so that nodes are next time
// printed from right to left
flag = 0;
// Decrement j
j--;
}
}
}
// Driver code
public static void main(String[] args)
{
Node root = new Node(20);
root.left = new Node(8);
root.right = new Node(22);
root.left.left = new Node(5);
root.left.right = new Node(3);
root.right.left = new Node(4);
root.right.right = new Node(25);
root.left.right.left = new Node(10);
root.left.right.right = new Node(14);
ReverseAntiClockWiseSpiral(root);
}
}
// This code is contributed by Prerna Saini.
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 anti clockwise # spiral traversal of a binary tree def ReverseAntiClockWiseSpiral(root): i = 1 j = height(root) # Flag to mark a change in the # direction of printing nodes flag = 1; while (i <= j): # If flag is zero print nodes # from right to left if (flag == 0): rightToLeft(root, i) # Set the value of flag as zero # so that nodes are next time # printed from left to right flag = 1 # Increment i i += 1 # If flag is one print nodes # from left to right else: leftToRight(root, j) # Set the value of flag as zero # so that nodes are next time # printed from right to left flag = 0 # Decrement j j -= 1 # Driver code if __name__=="__main__": root = Node(20) root.left = Node(8) root.right = Node(22) root.left.left = Node(5) root.left.right = Node(3) root.right.left = Node(4) root.right.right = Node(25) root.left.right.left = Node(10) root.left.right.right = Node(14) ReverseAntiClockWiseSpiral(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 anti clockwise spiral
// traversal of a binary tree
static void ReverseAntiClockWiseSpiral(Node root)
{
int i = 1;
int j = height(root);
// Flag to mark a change in the direction
// of printing nodes
int flag = 1;
while (i <= j)
{
// If flag is zero print nodes
// from right to left
if (flag == 0)
{
rightToLeft(root, i);
// Set the value of flag as zero
// so that nodes are next time
// printed from left to right
flag = 1;
// Increment i
i++;
}
// If flag is one print nodes
// from left to right
else
{
leftToRight(root, j);
// Set the value of flag as zero
// so that nodes are next time
// printed from right to left
flag = 0;
// Decrement j
j--;
}
}
}
// Driver code
public static void Main(String[] args)
{
Node root = new Node(20);
root.left = new Node(8);
root.right = new Node(22);
root.left.left = new Node(5);
root.left.right = new Node(3);
root.right.left = new Node(4);
root.right.right = new Node(25);
root.left.right.left = new Node(10);
root.left.right.right = new Node(14);
ReverseAntiClockWiseSpiral(root);
}
}
// This code has been contributed by 29AjayKumar
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 anti clockwise spiral
// traversal of a binary tree
function ReverseAntiClockWiseSpiral(root)
{
let i = 1;
let j = height(root);
// Flag to mark a change in the direction
// of printing nodes
let flag = 1;
while (i <= j)
{
// If flag is zero print nodes
// from right to left
if (flag == 0)
{
rightToLeft(root, i);
// Set the value of flag as zero
// so that nodes are next time
// printed from left to right
flag = 1;
// Increment i
i++;
}
// If flag is one print nodes
// from left to right
else
{
leftToRight(root, j);
// Set the value of flag as zero
// so that nodes are next time
// printed from right to left
flag = 0;
// Decrement j
j--;
}
}
}
let root = new Node(20);
root.left = new Node(8);
root.right = new Node(22);
root.left.left = new Node(5);
root.left.right = new Node(3);
root.right.left = new Node(4);
root.right.right = new Node(25);
root.left.right.left = new Node(10);
root.left.right.right = new Node(14);
ReverseAntiClockWiseSpiral(root);
</script>
Producción:
10 14 20 5 3 4 25 22 8
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