Обратный обход бинарного дерева по спирали по часовой стрелке
Опубликовано: 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 return
|