Recorrido en espiral antihorario inverso de un árbol binario

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *