Dado un árbol binario, la tarea es imprimir los Nodes del árbol en forma de espiral en sentido antihorario.
Ejemplos:
Input:
1
/ \
2 3
/ \ / \
4 5 6 7
Output: 1 4 5 6 7 3 2
Input:
1
/ \
2 3
/ / \
4 5 6
/ \ / / \
7 8 9 10 11
Output: 1 7 8 9 10 11 3 2 4 5 6
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. Usaremos otra bandera variable y la inicializaremos a 0. Ahora, en el ciclo while, verificaremos una condición de que si la bandera es igual a 0, recorreremos el árbol de derecha a izquierda y marcaremos la bandera como 1 para que la próxima vez atraviesemos la árbol de izquierda a derecha y luego incrementar el valor de i para que la próxima vez visitemos el nivel justo debajo del nivel actual. Además, cuando atravesemos el nivel desde abajo, marcaremos la banderacomo 0 para que la próxima vez atravesemos el árbol de izquierda a derecha y luego disminuyamos el valor de j para que la próxima vez visitemos el nivel justo por encima 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 anti clockwise spiral
// traversal of a binary tree
void antiClockWiseSpiral(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, 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(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->right->left = new Node(5);
root->right->right = new Node(7);
root->left->left->left = new Node(10);
root->left->left->right = new Node(11);
root->right->right->left = new Node(8);
antiClockWiseSpiral(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 anti clockwise spiral
// traversal of a binary tree
static void antiClockWiseSpiral(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, 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(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.right.left = new Node(5);
root.right.right = new Node(7);
root.left.left.left = new Node(10);
root.left.left.right = new Node(11);
root.right.right.left = new Node(8);
antiClockWiseSpiral(root);
}
}
// This code is contributed by Prerna Saini.
Python3
# Python3 implementation of the approach # Binary tree node class newNode: # Constructor to create a newNode def __init__(self, data): self.data = data self.left = None self.right = None self.visited = False # 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 anti clockwise spiral # traversal of a binary tree def antiClockWiseSpiral(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, 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 = newNode(1) root.left = newNode(2) root.right = newNode(3) root.left.left = newNode(4) root.right.left = newNode(5) root.right.right = newNode(7) root.left.left.left = newNode(10) root.left.left.right = newNode(11) root.right.right.left = newNode(8) antiClockWiseSpiral(root) # This code is contributed by # SHUBHAMSINGH10
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 anti clockwise spiral
// traversal of a binary tree
static void antiClockWiseSpiral( 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, 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(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.right.left = new Node(5);
root.right.right = new Node(7);
root.left.left.left = new Node(10);
root.left.left.right = new Node(11);
root.right.right.left = new Node(8);
antiClockWiseSpiral(root);
}
}
//This code is contributed by Arnab Kundu
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 anti clockwise spiral
// traversal of a binary tree
function antiClockWiseSpiral(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, 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(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.right.left = new Node(5);
root.right.right = new Node(7);
root.left.left.left = new Node(10);
root.left.left.right = new Node(11);
root.right.right.left = new Node(8);
antiClockWiseSpiral(root);
</script>
Producción:
1 10 11 8 3 2 4 5 7
Otro enfoque:
el enfoque anterior tiene una complejidad O (n ^ 2) en el peor de los casos debido a que se llama al nivel de impresión cada vez. Una mejora sobre esto puede ser almacenar los Nodes de nivel y usarlos para imprimir.
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
struct Node {
struct Node* left;
struct Node* right;
int data;
Node(int data)
{
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
void antiClockWiseSpiral(struct Node* root)
{
// Initialize the queue
queue<Node*> q;
// Add the root node
q.push(root);
// Initialize the vector
vector<Node*> topone;
// Until queue is not empty
while (!q.empty()) {
int len = q.size();
// len is greater than zero
while (len > 0) {
Node* nd = q.front();
q.pop();
if (nd != NULL) {
topone.push_back(nd);
if (nd->right != NULL)
q.push(nd->right);
if (nd->left != NULL)
q.push(nd->left);
}
len--;
}
topone.push_back(NULL);
}
bool top = true;
int l = 0, r = (int)topone.size() - 2;
while (l < r) {
if (top) {
while (l < (int)topone.size()) {
Node* nd = topone[l++];
if (nd == NULL) {
break;
}
cout << nd->data << " ";
}
}
else {
while (r >= l) {
Node* nd = topone[r--];
if (nd == NULL)
break;
cout << nd->data << " ";
}
}
top = !top;
}
}
// Build Tree
int main()
{
/*
1
2 3
4 5 7
10 11 8
*/
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(5);
root->right->right = new Node(7);
root->left->left->left = new Node(10);
root->left->left->right = new Node(11);
root->right->right->left = new Node(8);
antiClockWiseSpiral(root);
return 0;
}
Java
// Java implementation of the above approach
import java.io.*;
import java.util.*;
class GFG {
// Structure of each node
class Node {
int val;
Node left, right;
Node(int val)
{
this.val = val;
this.left = this.right = null;
}
}
private void work(Node root)
{
// Initialize queue
Queue<Node> q = new LinkedList<>();
// Add the root node
q.add(root);
// Initialize the vector
Vector<Node> topone = new Vector<>();
// Until queue is not empty
while (!q.isEmpty()) {
int len = q.size();
// len is greater than zero
while (len > 0) {
Node nd = q.poll();
if (nd != null) {
topone.add(nd);
if (nd.right != null)
q.add(nd.right);
if (nd.left != null)
q.add(nd.left);
}
len--;
}
topone.add(null);
}
boolean top = true;
int l = 0, r = topone.size() - 2;
while (l < r) {
if (top) {
while (l < topone.size()) {
Node nd = topone.get(l++);
if (nd == null) {
break;
}
System.out.print(nd.val + " ");
}
}
else {
while (r >= l) {
Node nd = topone.get(r--);
if (nd == null)
break;
System.out.print(nd.val + " ");
}
}
top = !top;
}
}
// Build Tree
public void solve()
{
/*
1
2 3
4 5 7
10 11 8
*/
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(5);
root.right.right = new Node(7);
root.left.left.left = new Node(10);
root.left.left.right = new Node(11);
root.right.right.left = new Node(8);
// Function call
work(root);
}
// Driver Code
public static void main(String[] args)
{
GFG t = new GFG();
t.solve();
}
}
Python3
# Python 3 implementation of the above approach from collections import deque as dq class Node: def __init__(self, data): self.data = data self.left = None self.right = None def antiClockWiseSpiral(root): # Initialize the queue q=dq([root]) # Initialize the list topone=[] # Until queue is not empty while (q): l = len(q) # l is greater than zero while (l > 0): nd = q.popleft() if (nd != None): topone.append(nd) if (nd.right != None): q.append(nd.right) if (nd.left != None): q.append(nd.left) l-=1 topone.append(None) top = True l = 0; r = len(topone) - 2 while (l < r): if (top): while (l < len(topone)): nd = topone[l] l+=1 if (nd == None): break print(nd.data,end=" ") else: while (r >= l): nd = topone[r] r-=1 if (nd == None): break print(nd.data,end=" ") top = not top print() # Build Tree if __name__ == '__main__': # 1 # 2 3 # 4 5 7 # 10 11 8 root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.right.left = Node(5) root.right.right = Node(7) root.left.left.left = Node(10) root.left.left.right = Node(11) root.right.right.left = Node(8) antiClockWiseSpiral(root)
Javascript
<script>
// JavaScript code to implement the above approach
class Node {
constructor(data){
this.data = data;
this.left = null,this.right = null;
}
}
function antiClockWiseSpiral(root){
// Initialize the queue
let q = [root]
// Initialize the list
let topone=[]
// Until queue is not empty
while (q.length>0){
let l = q.length
// l is greater than zero
while (l > 0){
let nd = q.shift()
if (nd != null){
topone.push(nd)
if (nd.right != null)
q.push(nd.right)
if (nd.left != null)
q.push(nd.left)
}
l-=1
}
topone.push(null)
}
let top = true
let l = 0,r = topone.length - 2
while (l < r){
if (top){
while (l < topone.length){
let nd = topone[l]
l+=1
if (nd == null)
break
document.write(nd.data," ")
}
}
else{
while (r >= l){
let nd = topone[r]
r-=1
if (nd == null)
break
document.write(nd.data," ")
}
}
top = top^1
}
document.write("</br>")
}
// driver code
// Build Tree
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(5)
root.right.right = new Node(7)
root.left.left.left = new Node(10)
root.left.left.right = new Node(11)
root.right.right.left = new Node(8)
antiClockWiseSpiral(root)
// code is contributed by shinjanpatra
</script>
Producción:
1 10 11 8 3 2 4 5 7
Complejidad temporal: O(N)
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