Обход порядка уровней со сменой направления через каждые два уровня | Рекурсивный подход
Опубликовано: 16 Января, 2022
Для двоичного дерева распечатайте обход порядка уровней таким образом, чтобы первые два уровня печатались слева направо, следующие два уровня - справа налево, затем следующие два - слева направо и так далее. Таким образом, проблема состоит в том, чтобы изменить направление обхода порядка уровней двоичного дерева на противоположное после каждых двух уровней.
Примеры:
Вход:
1
/
2 3
/ /
4 5 6 7
/ / / /
8 9 3 1 4 2 7 2
/ /
16 17 18 19
Выход:
1
2 3
7 6 5 4
2 7 2 4 1 3 9 8
16 17 18 19
В приведенном выше примере первые два уровня
печатаются слева направо, следующие два
уровни печатаются справа налево,
а затем последний уровень печатается из
слева направо.
Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.
Подход: в предыдущем посте обход порядка уровней с использованием очереди и стека был выполнен для печати элементов. Здесь использовался рекурсивный метод для печати элементов на каждом уровне. Пройдите каждый уровень в дереве, на каждом уровне проверьте направление. Используйте флаг, чтобы узнать направление обхода дерева. Если флаг установлен в значение true , распечатайте узлы справа налево на определенном уровне. Если флаг установлен в значение false , распечатайте узлы на этом уровне слева направо. Первоначально флаг установлен в False, после каждых 2 уровней flag меняет свое значение на true и наоборот.
Below is the implementation of the above approach.
C++
// C++ program level order traversal// with direction change// after every two levels#include <bits/stdc++.h>using namespace std; struct node { int data; node *left, *right;} * temp; // inserts new nodenode* newNode(int data){ temp = new node; temp->data = data; temp->left = temp->right = NULL; return temp;} // function to print current levelvoid printCurrLevel(node* root, int level, bool flag){ if (!root) return; if (level == 1) { cout << root->data << " "; return; } else { // If the flag is true, we have to print // level from RIGHT to LEFT. if (flag) { printCurrLevel(root->right, level - 1, flag); printCurrLevel(root->left, level - 1, flag); } // If the flag is false, we have to print // level from LEFT to RIGHT. else { printCurrLevel(root->left, level - 1, flag); printCurrLevel(root->right, level - 1, flag); } }} // This function returns the height of tree.int height(node* root){ if (!root) return 0; // left subtree int lh = height(root->left); // right subtree int rh = height(root->right); return 1 + max(lh, rh);} // Function to traverse level-wise and// print nodesvoid modifiedLevelOrder(node* root){ int h = height(root); // Variable to choose direction. bool flag = false; for (int i = 1; i <= h; i++) { printCurrLevel(root, i, flag); cout << endl; // change direction after every two levels. if (i % 2 == 0) flag = !flag; }} // Driver Codeint main(){ // create tree that is given // in the example node* root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); root->right->left = newNode(6); root->right->right = newNode(7); root->left->left->left = newNode(8); root->left->left->right = newNode(9); root->left->right->left = newNode(3); root->left->right->right = newNode(1); root->right->left->left = newNode(4); root->right->left->right = newNode(2); root->right->right->left = newNode(7); root->right->right->right = newNode(2); root->left->right->left->left = newNode(16); root->left->right->left->right = newNode(17); root->right->left->right->left = newNode(18); root->right->right->left->right = newNode(19); modifiedLevelOrder(root); return 0;} |
Java
// Java implementation of above idea import java.util.*; class GFG { static class node { int data; node left, right; } static node temp; // inserts new node static node newNode(int data) { temp = new node(); temp.data = data; temp.left = temp.right = null; return temp; } // function to print current level static void printCurrLevel(node root, int level, boolean flag) { if (root == null) return; if (level == 1) { System.out.print(root.data + " "); return; } else { // If the flag is true, we have to print // level from RIGHT to LEFT. if (flag) { printCurrLevel(root.right, level - 1, flag); printCurrLevel(root.left, level - 1, flag); } // If the flag is false, we have to print // level from LEFT to RIGHT. else { printCurrLevel(root.left, level - 1, flag); printCurrLevel(root.right, level - 1, flag); } } } // This function returns the height of tree. static int height(node root) { if (root == null) return 0; // left subtree int lh = height(root.left); // right subtree int rh = height(root.right); return 1 + Math.max(lh, rh); } // Function to traverse level-wise and // print nodes static void modifiedLevelOrder(node root) { int h = height(root); // Variable to choose direction. boolean flag = false; for (int i = 1; i <= h; i++) { printCurrLevel(root, i, flag); System.out.println(""); // change direction after every two levels. if (i % 2 == 0) flag = !flag; } } // Driver Code public static void main(String[] args){ // create tree that is given // in the example node root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(5); root.right.left = newNode(6); root.right.right = newNode(7); root.left.left.left = newNode(8); root.left.left.right = newNode(9); root.left.right.left = newNode(3); root.left.right.right = newNode(1); root.right.left.left = newNode(4); root.right.left.right = newNode(2); root.right.right.left = newNode(7); root.right.right.right = newNode(2); root.left.right.left.left = newNode(16); root.left.right.left.right = newNode(17); root.right.left.right.left = newNode(18); root.right.right.left.right = newNode(19); modifiedLevelOrder(root); }} // This code is contributed by Princi Singh |
Python3
# Python3 program level order traversal with# direction change after every two levels class Node: def __init__(self, data): self.data = data self.left = None self.right = None # function to print current level def printCurrLevel(root, level, flag): if root == None: return if level == 1: print(root.data, end = " ") return else: # If the flag is true, we have to # print level from RIGHT to LEFT. if flag: printCurrLevel(root.right, level - 1, flag) printCurrLevel(root.left, level - 1, flag) # If the flag is false, we have to # print level from LEFT to RIGHT. else: printCurrLevel(root.left, level - 1, flag) printCurrLevel(root.right, level - 1, flag) # This function returns the # height of tree. def height(root): if root == None: return 0 # left subtree lh = height(root.left) # right subtree rh = height(root.right) return 1 + max(lh, rh) # Function to traverse level-wise # and print nodes def modifiedLevelOrder(root): h = height(root) # Variable to choose direction. flag = False for i in range(1, h + 1): printCurrLevel(root, i, flag) print() # change direction after every # two levels. if i % 2 == 0: flag = not flag # Driver Code if __name__ == "__main__": # create tree that is given # in the example root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5) root.right.left = Node(6) root.right.right = Node(7) root.left.left.left = Node(8) root.left.left.right = Node(9) root.left.right.left = Node(3) root.left.right.right = Node(1) root.right.left.left = Node(4) root.right.left.right = Node(2) root.right.right.left = Node(7) root.right.right.right = Node(2) root.left.right.left.left = Node(16) root.left.right.left.right = Node(17) root.right.left.right.left = Node(18) root.right.right.left.right = Node(19) modifiedLevelOrder(root) # This code is contributed by Rituraj Jain |
C#
// C# implementation of above idea using System; class GFG { public class node { public int data; public node left, right; } static node temp; // inserts new node static node newNode(int data) { temp = new node(); temp.data = data; temp.left = temp.right = null; return temp; } // function to print current level static void printCurrLevel(node root, int level, Boolean flag) { if (root == null) return; if (level == 1) { Console.Write(root.data + " "); return; } else { // If the flag is true, we have to print // level from RIGHT to LEFT. if (flag) { printCurrLevel(root.right, level - 1, flag); printCurrLevel(root.left, level - 1, flag);
|