Dado un árbol binario, imprima el recorrido de orden de nivel de tal manera que los primeros dos niveles se impriman de izquierda a derecha, los siguientes dos niveles se impriman de derecha a izquierda, luego los dos siguientes de izquierda a derecha y así sucesivamente. Entonces, el problema es invertir la dirección del recorrido del orden de niveles del árbol binario después de cada dos niveles.
Ejemplos:
Input: 1 / \ 2 3 / \ / \ 4 5 6 7 / \ / \ / \ / \ 8 9 3 1 4 2 7 2 / / \ \ 16 17 18 19 Output: 1 2 3 7 6 5 4 2 7 2 4 1 3 9 8 16 17 18 19 In the above example, first two levels are printed from left to right, next two levels are printed from right to left, and then last level is printed from left to right.
Enfoque:
Hacemos uso de la cola y la pila aquí. La cola se utiliza para realizar un recorrido de orden de nivel normal. Stack se utiliza para invertir la dirección de recorrido después de cada dos niveles.
Mientras se realiza un recorrido de orden de niveles normal, los primeros dos Nodes de niveles se imprimen en el momento en que se extraen de la cola. Para los siguientes dos niveles, en lugar de imprimir los Nodes, los colocamos en la pila. Cuando aparecen todos los Nodes del nivel actual, imprimimos los Nodes en la pila. De esta forma, imprimimos los Nodes en orden de derecha a izquierda haciendo uso de la pila. Ahora, para los siguientes dos niveles, nuevamente hacemos un recorrido de orden de nivel normal para imprimir Nodes de izquierda a derecha. Luego, para los siguientes dos Nodes, hacemos uso de la pila para lograr el orden de derecha a izquierda.
De esta manera, lograremos el cruce de orden de nivel modificado deseado haciendo uso de la cola y la pila.
C++
// CPP program to print Zig-Zag traversal // in groups of size 2. #include <iostream> #include <queue> #include <stack> using namespace std; // A Binary Tree Node struct Node { struct Node* left; int data; struct Node* right; }; /* Function to print the level order of given binary tree. Direction of printing level order traversal of binary tree changes after every two levels */ void modifiedLevelOrder(struct Node* node) { // For null root if (node == NULL) return; if (node->left == NULL && node->right == NULL) { cout << node->data; return; } // Maintain a queue for normal // level order traversal queue<Node*> myQueue; /* Maintain a stack for printing nodes in reverse order after they are popped out from queue.*/ stack<Node*> myStack; struct Node* temp = NULL; // sz is used for storing the count // of nodes in a level int sz; // Used for changing the direction // of level order traversal int ct = 0; // Used for changing the direction // of level order traversal bool rightToLeft = false; // Push root node to the queue myQueue.push(node); // Run this while loop till queue got empty while (!myQueue.empty()) { ct++; sz = myQueue.size(); // Do a normal level order traversal for (int i = 0; i < sz; i++) { temp = myQueue.front(); myQueue.pop(); /*For printing nodes from left to right, simply print the nodes in the order in which they are being popped out from the queue.*/ if (rightToLeft == false) cout << temp->data << " "; /* For printing nodes from right to left, push the nodes to stack instead of printing them.*/ else myStack.push(temp); if (temp->left) myQueue.push(temp->left); if (temp->right) myQueue.push(temp->right); } if (rightToLeft == true) { // for printing the nodes in order // from right to left while (!myStack.empty()) { temp = myStack.top(); myStack.pop(); cout << temp->data << " "; } } /*Change the direction of printing nodes after every two levels.*/ if (ct == 2) { rightToLeft = !rightToLeft; ct = 0; } cout << "\n"; } } // Utility function to create a new tree node Node* newNode(int data) { Node* temp = new Node; temp->data = data; temp->left = temp->right = NULL; return temp; } // Driver program to test above functions int main() { // Let us create binary tree 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 program to print Zig-Zag traversal // in groups of size 2. import java.util.*; class GFG { // A Binary Tree Node static class Node { Node left; int data; Node right; }; /* Function to print the level order of given binary tree. Direction of printing level order traversal of binary tree changes after every two levels */ static void modifiedLevelOrder(Node node) { // For null root if (node == null) return; if (node.left == null && node.right == null) { System.out.print(node.data); return; } // Maintain a queue for normal // level order traversal Queue<Node> myQueue = new LinkedList<>(); /* Maintain a stack for printing nodes in reverse order after they are popped out from queue.*/ Stack<Node> myStack = new Stack<>(); Node temp = null; // sz is used for storing // the count of nodes in a level int sz; // Used for changing the direction // of level order traversal int ct = 0; // Used for changing the direction // of level order traversal boolean rightToLeft = false; // Push root node to the queue myQueue.add(node); // Run this while loop till queue got empty while (!myQueue.isEmpty()) { ct++; sz = myQueue.size(); // Do a normal level order traversal for (int i = 0; i < sz; i++) { temp = myQueue.peek(); myQueue.remove(); /*For printing nodes from left to right, simply print the nodes in the order in which they are being popped out from the queue.*/ if (rightToLeft == false) System.out.print(temp.data + " "); /* For printing nodes from right to left, push the nodes to stack instead of printing them.*/ else myStack.push(temp); if (temp.left != null) myQueue.add(temp.left); if (temp.right != null) myQueue.add(temp.right); } if (rightToLeft == true) { // for printing the nodes in order // from right to left while (!myStack.isEmpty()) { temp = myStack.peek(); myStack.pop(); System.out.print(temp.data + " "); } } /*Change the direction of printing nodes after every two levels.*/ if (ct == 2) { rightToLeft = !rightToLeft; ct = 0; } System.out.print("\n"); } } // Utility function to create a new tree node static Node newNode(int data) { Node temp = new Node(); temp.data = data; temp.left = temp.right = null; return temp; } // Driver Code public static void main(String[] args) { // Let us create binary tree 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 29AjayKumar
Python3
# A Binary Tree Node from collections import deque class Node: def __init__(self, x): self.data = x self.left = None self.right = None # /* Function to print level order of # given binary tree. Direction of printing # level order traversal of binary tree changes # after every two levels */ def modifiedLevelOrder(node): # For null root if (node == None): return if (node.left == None and node.right == None): print(node.data, end = " ") return # Maintain a queue for normal # level order traversal myQueue = deque() # /* Maintain a stack for printing nodes in reverse # order after they are popped out from queue.*/ myStack = [] temp = None # sz is used for storing the count # of nodes in a level sz = 0 # Used for changing the direction # of level order traversal ct = 0 # Used for changing the direction # of level order traversal rightToLeft = False # Push root node to the queue myQueue.append(node) # Run this while loop till queue got empty while (len(myQueue) > 0): ct += 1 sz = len(myQueue) # Do a normal level order traversal for i in range(sz): temp = myQueue.popleft() # /*For printing nodes from left to right, # simply print nodes in the order in which # they are being popped out from the queue.*/ if (rightToLeft == False): print(temp.data,end=" ") # /* For printing nodes # from right to left, # push the nodes to stack # instead of printing them.*/ else: myStack.append(temp) if (temp.left): myQueue.append(temp.left) if (temp.right): myQueue.append(temp.right) if (rightToLeft == True): # for printing the nodes in order # from right to left while (len(myStack) > 0): temp = myStack[-1] del myStack[-1] print(temp.data, end = " ") # /*Change the direction of printing # nodes after every two levels.*/ if (ct == 2): rightToLeft = not rightToLeft ct = 0 print() # Driver program to test above functions if __name__ == '__main__': # Let us create binary tree 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 mohit kumar 29.
C#
// C# program to print Zig-Zag traversal // in groups of size 2. using System; using System.Collections.Generic; class GFG { // A Binary Tree Node public class Node { public Node left; public int data; public Node right; }; /* Function to print the level order of given binary tree. Direction of printing level order traversal of binary tree changes after every two levels */ static void modifiedLevelOrder(Node node) { // For null root if (node == null) return; if (node.left == null && node.right == null) { Console.Write(node.data); return; } // Maintain a queue for // normal level order traversal Queue<Node> myQueue = new Queue<Node>(); /* Maintain a stack for printing nodes in reverse order after they are popped out from queue.*/ Stack<Node> myStack = new Stack<Node>(); Node temp = null; // sz is used for storing // the count of nodes in a level int sz; // Used for changing the direction // of level order traversal int ct = 0; // Used for changing the direction // of level order traversal bool rightToLeft = false; // Push root node to the queue myQueue.Enqueue(node); // Run this while loop // till queue got empty while (myQueue.Count != 0) { ct++; sz = myQueue.Count; // Do a normal level order traversal for (int i = 0; i < sz; i++) { temp = myQueue.Peek(); myQueue.Dequeue(); /* For printing nodes from left to right, simply print the nodes in the order in which they are being popped out from the queue.*/ if (rightToLeft == false) Console.Write(temp.data + " "); /* For printing nodes from right to left, push the nodes to stack instead of printing them.*/ else myStack.Push(temp); if (temp.left != null) myQueue.Enqueue(temp.left); if (temp.right != null) myQueue.Enqueue(temp.right); } if (rightToLeft == true) { // for printing the nodes in order // from right to left while (myStack.Count != 0) { temp = myStack.Peek(); myStack.Pop(); Console.Write(temp.data + " "); } } /*Change the direction of printing nodes after every two levels.*/ if (ct == 2) { rightToLeft = !rightToLeft; ct = 0; } Console.Write("\n"); } } // Utility function to create a new tree node static Node newNode(int data) { Node temp = new Node(); temp.data = data; temp.left = temp.right = null; return temp; } // Driver Code public static void Main(String[] args) { // Let us create binary tree 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 Rajput-Ji
Javascript
<script> // Javascript program to print Zig-Zag traversal // in groups of size 2. // A Binary Tree Node class Node { constructor(data) { this.data = data; this.left = this.right=null; } } /* Function to print the level order of given binary tree. Direction of printing level order traversal of binary tree changes after every two levels */ function modifiedLevelOrder(node) { // For null root if (node == null) return; if (node.left == null && node.right == null) { document.write(node.data); return; } // Maintain a queue for normal // level order traversal let myQueue = []; /* Maintain a stack for printing nodes in reverse order after they are popped out from queue.*/ let myStack = []; let temp = null; // sz is used for storing // the count of nodes in a level let sz; // Used for changing the direction // of level order traversal let ct = 0; // Used for changing the direction // of level order traversal let rightToLeft = false; // Push root node to the queue myQueue.push(node); // Run this while loop till queue got empty while (myQueue.length != 0) { ct++; sz = myQueue.length; // Do a normal level order traversal for (let i = 0; i < sz; i++) { temp = myQueue.shift(); /*For printing nodes from left to right, simply print the nodes in the order in which they are being popped out from the queue.*/ if (rightToLeft == false) document.write(temp.data + " "); /* For printing nodes from right to left, push the nodes to stack instead of printing them.*/ else myStack.push(temp); if (temp.left != null) myQueue.push(temp.left); if (temp.right != null) myQueue.push(temp.right); } if (rightToLeft == true) { // for printing the nodes in order // from right to left while (myStack.length != 0) { temp = myStack.pop(); document.write(temp.data + " "); } } /*Change the direction of printing nodes after every two levels.*/ if (ct == 2) { rightToLeft = !rightToLeft; ct = 0; } document.write("<br>"); } } // Driver Code // Let us create binary tree let root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.left.right = new Node(5); root.right.left = new Node(6); root.right.right = new Node(7); root.left.left.left = new Node(8); root.left.left.right = new Node(9); root.left.right.left = new Node(3); root.left.right.right = new Node(1); root.right.left.left = new Node(4); root.right.left.right = new Node(2); root.right.right.left = new Node(7); root.right.right.right = new Node(2); root.left.right.left.left = new Node(16); root.left.right.left.right = new Node(17); root.right.left.right.left = new Node(18); root.right.right.left.right = new Node(19); modifiedLevelOrder(root); // This code is contributed by unknown2108 </script>
C++
// CPP program to print Zig-Zag traversal // in groups of size 2. #include <iostream> #include <stack> #include <queue> using namespace std; #define LEFT 0 #define RIGHT 1 #define ChangeDirection(Dir) ((Dir) = 1 - (Dir)) // A Binary Tree Node struct node { int data; struct node *left, *right; }; // Utility function to create a new tree node node* newNode(int data) { node* temp = new node; temp->data = data; temp->left = temp->right = NULL; return temp; } /* Function to print the level order of given binary tree. Direction of printing level order traversal of binary tree changes after every two levels */ void modifiedLevelOrder(struct node *root) { if (!root) return ; int dir = LEFT; struct node *temp; queue <struct node *> Q; stack <struct node *> S; S.push(root); // Run this while loop till queue got empty while (!Q.empty() || !S.empty()) { while (!S.empty()) { temp = S.top(); S.pop(); cout << temp->data << " "; if (dir == LEFT) { if (temp->left) Q.push(temp->left); if (temp->right) Q.push(temp->right); } /* For printing nodes from right to left, push the nodes to stack instead of printing them.*/ else { if (temp->right) Q.push(temp->right); if (temp->left) Q.push(temp->left); } } cout << endl; // for printing the nodes in order // from right to left while (!Q.empty()) { temp = Q.front(); Q.pop(); cout << temp->data << " "; if (dir == LEFT) { if (temp->left) S.push(temp->left); if (temp->right) S.push(temp->right); } else { if (temp->right) S.push(temp->right); if (temp->left) S.push(temp->left); } } cout << endl; // Change the direction of traversal. ChangeDirection(dir); } } // Driver program to test above functions int main() { // Let us create binary tree 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 program to print Zig-Zag traversal // in groups of size 2. import java.util.*; class GFG { static final int LEFT = 0; static final int RIGHT = 1; static int ChangeDirection(int Dir) { Dir = 1 - Dir; return Dir; } // A Binary Tree Node static class node { int data; node left, right; }; // Utility function to create a new tree node static node newNode(int data) { node temp = new node(); temp.data = data; temp.left = temp.right = null; return temp; } /* Function to print the level order of given binary tree. Direction of printing level order traversal of binary tree changes after every two levels */ static void modifiedLevelOrder(node root) { if (root == null) return ; int dir = LEFT; node temp; Queue <node > Q = new LinkedList<>(); Stack <node > S = new Stack<>(); S.add(root); // Run this while loop till queue got empty while (!Q.isEmpty() || !S.isEmpty()) { while (!S.isEmpty()) { temp = S.peek(); S.pop(); System.out.print(temp.data + " "); if (dir == LEFT) { if (temp.left != null) Q.add(temp.left); if (temp.right != null) Q.add(temp.right); } /* For printing nodes from right to left, push the nodes to stack instead of printing them.*/ else { if (temp.right != null) Q.add(temp.right); if (temp.left != null) Q.add(temp.left); } } System.out.println(); // for printing the nodes in order // from right to left while (!Q.isEmpty()) { temp = Q.peek(); Q.remove(); System.out.print(temp.data + " "); if (dir == LEFT) { if (temp.left != null) S.add(temp.left); if (temp.right != null) S.add(temp.right); } else { if (temp.right != null) S.add(temp.right); if (temp.left != null) S.add(temp.left); } } System.out.println(); // Change the direction of traversal. dir = ChangeDirection(dir); } } // Driver code public static void main(String[] args) { // Let us create binary tree 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 Rajput-Ji
Python3
# Python3 program to print Zig-Zag traversal # in groups of size 2. LEFT = 0 RIGHT = 1 def ChangeDirection(Dir): Dir = 1 - Dir return Dir # A Binary Tree Node class node: # Constructor to set the data of # the newly created tree node def __init__(self, data): self.data = data self.left = None self.right = None """ Function to print the level order of given binary tree. Direction of printing level order traversal of binary tree changes after every two levels """ def modifiedLevelOrder(root): if (root == None): return Dir = LEFT Q = [] S = [] S.append(root) # Run this while loop till queue got empty while (len(Q) > 0 or len(S) > 0): while (len(S) > 0): temp = S[-1] S.pop() print(temp.data, end = " ") if (Dir == LEFT): if (temp.left != None): Q.append(temp.left) if (temp.right != None): Q.append(temp.right) else: if (temp.right != None): Q.append(temp.right) if (temp.left != None): Q.append(temp.left) print() # for printing the nodes in order # from right to left while len(Q) > 0: temp = Q[0] Q.pop(0) print(temp.data, end = " ") if (Dir == LEFT): if (temp.left != None): S.append(temp.left) if (temp.right != None): S.append(temp.right) else: if (temp.right != None): S.append(temp.right) if (temp.left != None): S.append(temp.left) print() # Change the direction of traversal. Dir = ChangeDirection(Dir) # Let us create binary tree 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 suresh07.
C#
// C# program to print Zig-Zag traversal // in groups of size 2. using System; using System.Collections.Generic; public class GFG { static readonly int LEFT = 0; static readonly int RIGHT = 1; static int ChangeDirection(int Dir) { Dir = 1 - Dir; return Dir; } // A Binary Tree Node public class node { public int data; public node left, right; }; // Utility function to create a new tree node static node newNode(int data) { node temp = new node(); temp.data = data; temp.left = temp.right = null; return temp; } /* Function to print the level order of given binary tree. Direction of printing level order traversal of binary tree changes after every two levels */ static void modifiedLevelOrder(node root) { if (root == null) return ; int dir = LEFT; node temp; Queue <node > Q = new Queue<node>(); Stack <node > S = new Stack<node>(); S.Push(root); // Run this while loop till queue got empty while (Q.Count!=0 || S.Count!=0) { while (S.Count!=0) { temp = S.Peek(); S.Pop(); Console.Write(temp.data + " "); if (dir == LEFT) { if (temp.left != null) Q.Enqueue(temp.left); if (temp.right != null) Q.Enqueue(temp.right); } /* For printing nodes from right to left, push the nodes to stack instead of printing them.*/ else { if (temp.right != null) Q.Enqueue(temp.right); if (temp.left != null) Q.Enqueue(temp.left); } } Console.WriteLine(); // for printing the nodes in order // from right to left while (Q.Count!=0) { temp = Q.Peek(); Q.Dequeue(); Console.Write(temp.data + " "); if (dir == LEFT) { if (temp.left != null) S.Push(temp.left); if (temp.right != null) S.Push(temp.right); } else { if (temp.right != null) S.Push(temp.right); if (temp.left != null) S.Push(temp.left); } } Console.WriteLine(); // Change the direction of traversal. dir = ChangeDirection(dir); } } // Driver code public static void Main(String[] args) { // Let us create binary tree 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 contributed by Rajput-Ji
Javascript
<script> // Javascript program to print Zig-Zag traversal // in groups of size 2. let LEFT = 0; let RIGHT = 1; // A Binary Tree Node function ChangeDirection(Dir) { Dir = 1 - Dir; return Dir; } class Node { // Utility function to create a new tree node constructor(data) { this.data=data; this.left=this.right=null; } } /* Function to print the level order of given binary tree. Direction of printing level order traversal of binary tree changes after every two levels */ function modifiedLevelOrder(root) { if (root == null) return ; let dir = LEFT; let temp; let Q = []; let S = []; S.push(root); // Run this while loop till queue got empty while (Q.length!=0 || S.length!=0) { while (S.length!=0) { temp = S.pop(); document.write(temp.data + " "); if (dir == LEFT) { if (temp.left != null) Q.push(temp.left); if (temp.right != null) Q.push(temp.right); } /* For printing nodes from right to left, push the nodes to stack instead of printing them.*/ else { if (temp.right != null) Q.push(temp.right); if (temp.left != null) Q.push(temp.left); } } document.write("<br>"); // for printing the nodes in order // from right to left while (Q.length!=0) { temp = Q[0]; Q.shift(); document.write(temp.data + " "); if (dir == LEFT) { if (temp.left != null) S.push(temp.left); if (temp.right != null) S.push(temp.right); } else { if (temp.right != null) S.push(temp.right); if (temp.left != null) S.push(temp.left); } } document.write("<br>"); // Change the direction of traversal. dir = ChangeDirection(dir); } } // Driver code // Let us create binary tree let root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.left.right = new Node(5); root.right.left = new Node(6); root.right.right = new Node(7); root.left.left.left = new Node(8); root.left.left.right = new Node(9); root.left.right.left = new Node(3); root.left.right.right = new Node(1); root.right.left.left = new Node(4); root.right.left.right = new Node(2); root.right.right.left = new Node(7); root.right.right.right = new Node(2); root.left.right.left.left = new Node(16); root.left.right.left.right = new Node(17); root.right.left.right.left = new Node(18); root.right.right.left.right = new Node(19); modifiedLevelOrder(root); // This code is contributed by patel2127 </script>
C++
// CPP program to implement above approach #include <bits/stdc++.h> using namespace std; // A Binary Tree Node struct node { int key; struct node *left, *right; }; // Utility function to create a new tree node node* newNode(int data) { node* temp = new node; temp->key = data; temp->left = temp->right = NULL; return temp; } vector<int> stack_struct; void print_level(node* root,int level,bool stack); // Function to calculate height int heightTree(node* root) { // Check if root is None if (root == NULL) return 0; else { int lheight = heightTree(root->left); int rheight = heightTree(root->right); // Check greater between // lheight and rheight if (lheight > rheight) return (1 + lheight); else return (1 + rheight); } } // Function to print 2 levels void print_2_levels(node* root) { // Check if root is None if(root==NULL) return; int height = heightTree(root); int count = 0; // Iterate from 1 to height for(int i=1;i<height+1;i++) { stack_struct = {}; // Check is count is less than 2 if (count < 2) print_level(root, i, false); else { print_level(root, i, true); // Iterate backwards from len(stack_struct)-1 // till 0 for(int i=stack_struct.size()-1;i>=0;i--) cout<< stack_struct[i]<<" "; if (count == 3) count = -1; } // Increment Counter count += 1; cout << "\n"; } } // Function to print level void print_level(node* root,int level,bool stack) { // Check if root is None if (root==NULL) return; // Check is level is 1 and stack is False if (level == 1 && stack == false) cout<< root->key<<" "; // Check if level is 1 and stack is True else if (level == 1 && stack == true) stack_struct.push_back(root->key); // Check if level is greater than 1 else if (level > 1) { print_level(root->left, level-1, stack); print_level(root->right, level-1, stack); } } // Driver program to test above functions int main() { // Let us create binary tree 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); cout<<"Different levels:\n"; //Function Call print_2_levels(root); return 0; } // THis code is contributed by Abhijeet Kumar(abhijeet19403)
Python3
# Python program for above approach # Node class class Node: def __init__(self, key): self.left = None self.right = None self.key = key # Function to calculate height def heightTree(root): # Check if root is None if root is None: return 0 else: lheight = heightTree(root.left) rheight = heightTree(root.right) # Check greater between # lheight and rheight if lheight > rheight: return 1 + lheight else: return 1 + rheight # Function to print 2 levels def print_2_levels(root): # Check if root is None if root is None: return height = heightTree(root) count = 0 # Iterate from 1 to height for i in range(1, height+1): global stack_struct stack_struct = [] # Check is count is less than 2 if count < 2: print_level(root, i, stack=False) else: print_level(root, i, stack=True) # Iterate backwards from len(stack_struct)-1 # till 0 for i in range(len(stack_struct)-1, -1, -1): print(stack_struct[i], end=' ') if count == 3: count = -1 # Increment Counter count += 1 print("") # Function to print level def print_level(root, level, stack=False): global stack_struct # Check if root is None if root is None: return # Check is level is 1 and stack is False if level == 1 and stack == False: print(root.key, end=' ') # Check if level is 1 and stack is True elif level == 1 and stack == True: stack_struct.append(root.key) # Check if level is greater than 1 elif level > 1: print_level(root.left, level-1, stack=stack) print_level(root.right, level-1, stack=stack) # Driver Code 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.left.right.left = Node(16) root.left.right.right.left = Node(17) root.left.right.right.right = Node(18) root.right.left.right.right = Node(19) print("Different levels:") # Function Call print_2_levels(root)
Javascript
<script> // JavaScript program for above approach // Node class class Node{ constructor(key){ this.left = null this.right = null this.key = key } } let stack_struct; // Function to calculate height function heightTree(root){ // Check if root is null if(root == null) return 0 else{ let lheight = heightTree(root.left) let rheight = heightTree(root.right) // Check greater between // lheight and rheight if(lheight > rheight) return 1 + lheight else return 1 + rheight } } // Function to print 2 levels function print_2_levels(root){ // Check if root is null if(root == null) return let height = heightTree(root) let count = 0 // Iterate from 1 to height for(let i=1;i<height+1;i++){ stack_struct = [] // Check is count is less than 2 if(count < 2) print_level(root, i, stack=false) else{ print_level(root, i, stack=true) // Iterate backwards from len(stack_struct)-1 // till 0 for(let i = stack_struct.length-1;i>=0;i--){ document.write(stack_struct[i],' ') } if(count == 3) count = -1 } // Increment Counter count += 1 document.write("</br>") } } // Function to print level function print_level(root, level, stack=false){ // Check if root is null if(root==null) return // Check is level is 1 and stack is False if(level == 1 && stack == false) document.write(root.key,' ') // Check if level is 1 and stack is True else if(level == 1 && stack == true) stack_struct.push(root.key) // Check if level is greater than 1 else if(level > 1){ print_level(root.left, level-1, stack=stack) print_level(root.right, level-1, stack=stack) } } // Driver Code let root = new Node(1) root.left = new Node(2) root.right = new Node(3) root.left.left = new Node(4) root.left.right = new Node(5) root.right.left = new Node(6) root.right.right = new Node(7) root.left.left.left = new Node(8) root.left.left.right = new Node(9) root.left.right.left = new Node(3) root.left.right.right = new Node(1) root.right.left.left = new Node(4) root.right.left.right = new Node(2) root.right.right.left = new Node(7) root.right.right.right = new Node(2) root.left.left.right.left = new Node(16) root.left.right.right.left = new Node(17) root.left.right.right.right = new Node(18) root.right.left.right.right = new Node(19) document.write("Different levels:","<br>") // Function Call print_2_levels(root) // This code is contributed by shinjanpatra </script>
Publicación traducida automáticamente
Artículo escrito por Ashish Jindal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA