Обратный обход бинарного дерева по спирали по часовой стрелке

Опубликовано: 23 Января, 2022

Учитывая двоичное дерево. Задача состоит в том, чтобы напечатать круговой обход заданного двоичного дерева в обратном порядке по часовой стрелке.
Обратный обход по часовой стрелке означает обход дерева по часовой стрелке по спирали, начиная снизу, а не сверху корневого узла.
Примеры:

 Вход : 
          1
         / 
        2 3
       /  
      4 5 6
         / / 
        7 8 9
Выход: 9 8 7 1 6 5 4 2 3

Вход :
           20
         / 
        8 22
      /  / 
     5 3 4 25
          / 
         10 14
Выход: 14 10 20 25 4 3 5 8 22



Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход: идея состоит в том, чтобы использовать две переменные i, инициализированные значением 1 и j, инициализированные высотой дерева, и запустить цикл while, который не прерывается, пока i не станет больше j .

  • Используйте другую переменную flag и инициализируйте ее значением 0. Теперь в цикле while проверьте условие, что если flag равен 0, то перемещаться по дереву справа налево и отмечать флаг как 1, чтобы в следующий раз мы проходили дерево слева направо. правильно, это сделано для сохранения порядка обхода спирали по часовой стрелке.
  • Затем уменьшите значение j, чтобы в следующий раз посетить уровень чуть выше текущего.
  • Также, когда мы будем проходить уровень сверху, мы отметим флаг как 0, чтобы в следующий раз пройти по дереву справа налево, а затем увеличить значение i, чтобы в следующий раз мы посетили уровень чуть ниже текущего уровня.
  • Повторяйте весь процесс до тех пор, пока двоичное дерево не будет полностью пройдено.

Below is the implementation of the above approach:

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