Обратный обход двоичного дерева по спирали против часовой стрелки
Учитывая двоичное дерево, задача состоит в том, чтобы распечатать узлы дерева по обратной спирали против часовой стрелки.
Примеры:
Вход : 1 / 2 3 / 4 5 6 / / 7 8 9 Выход: 7 8 9 1 4 5 6 3 2 Вход : 20 / 8 22 / / 5 3 4 25 / 10 14 Выход: 10 14 20 5 3 4 25 22 8
Подход: идея состоит в том, чтобы использовать две переменные i, инициализированные значением 1 и j, инициализированные высотой дерева, и запустить цикл while, который не прерывается, пока i не станет больше j. Мы воспользуемся другим флагом переменной и инициализируем его значением 1. Теперь в цикле while мы проверим условие: если flag равен 1, мы будем обходить дерево слева направо и помечать флаг как 0, чтобы в следующий раз пройти через tree справа налево, а затем уменьшите значение j, чтобы в следующий раз мы посетили уровень чуть выше текущего. Также, когда мы будем проходить уровень сверху, мы отметим флаг как 1, чтобы в следующий раз пройти по дереву слева направо, а затем увеличить значение 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 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 &nbs
РЕКОМЕНДУЕМЫЕ СТАТЬИ |