Dado un árbol binario, la tarea es imprimir el orden en zigzag inverso del árbol.
Ejemplos:
Input:
1
/ \
2 3
/ \ \
4 5 6
Output: 6 5 4 2 3 1
Input:
5
/ \
9 3
/ \
6 4
/ \
8 7
Output: 7 8 6 4 3 9 5
Enfoque: La idea es atravesar el árbol en orden de nivel inverso pero con una ligera modificación. Usaremos una bandera variable e inicialmente estableceremos su valor en uno. A medida que completamos el recorrido del árbol en orden de nivel inverso, de derecha a izquierda estableceremos el valor de la bandera en cero, de modo que la próxima vez que atravesemos el árbol de izquierda a derecha y cuando completemos el recorrido establezcamos su valor de nuevo en una. Repetiremos todo este paso hasta que hayamos recorrido el Árbol Binario por completo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to print reverse
// zigzag order of binary tree
#include <bits/stdc++.h>
using namespace std;
// Binary tree node
struct node {
struct node* left;
struct node* right;
int data;
};
// Function to create a new
// Binary node
struct node* newNode(int data)
{
struct node* temp = new node;
temp->data = data;
temp->left = NULL;
temp->right = NULL;
return temp;
}
// Recursive Function to find height
// of binary tree
int HeightOfTree(struct node* root)
{
if (root == NULL)
return 0;
// Compute the height of each subtree
int lheight = HeightOfTree(root->left);
int rheight = HeightOfTree(root->right);
// Return the maximum of two
return max(lheight + 1, rheight + 1);
}
// Function to Print nodes from right to left
void Print_Level_Right_To_Left(struct node* root, int level)
{
if (root == NULL)
return;
if (level == 1)
cout << root->data << " ";
else if (level > 1) {
Print_Level_Right_To_Left(root->right, level - 1);
Print_Level_Right_To_Left(root->left, level - 1);
}
}
// Function to Print nodes from left to right
void Print_Level_Left_To_Right(struct node* root, int level)
{
if (root == NULL)
return;
if (level == 1)
cout << root->data << " ";
else if (level > 1) {
Print_Level_Left_To_Right(root->left, level - 1);
Print_Level_Left_To_Right(root->right, level - 1);
}
}
// Function to print Reverse zigzag of
// a Binary tree
void PrintReverseZigZag(struct node* root)
{
// Flag is used to mark the change
// in level
int flag = 1;
// Height of tree
int height = HeightOfTree(root);
for (int i = height; i >= 1; i--) {
// If flag value is one print nodes
// from right to left
if (flag == 1) {
Print_Level_Right_To_Left(root, i);
// Mark flag as zero so that next time
// tree is traversed from left to right
flag = 0;
}
// If flag is zero print nodes
// from left to right
else if (flag == 0) {
Print_Level_Left_To_Right(root, i);
// Mark flag as one so that next time
// nodes are printed from right to left
flag = 1;
}
}
}
// Driver code
int main()
{
struct node* root = newNode(5);
root->left = newNode(9);
root->right = newNode(3);
root->left->left = newNode(6);
root->right->right = newNode(4);
root->left->left->left = newNode(8);
root->left->left->right = newNode(7);
PrintReverseZigZag(root);
return 0;
}
Java
// Java program to print reverse
// zigzag order of binary tree
class GfG
{
// Binary tree node
static class node
{
node left;
node right;
int data;
}
// Function to create a new
// Binary node
static node newNode(int data)
{
node temp = new node();
temp.data = data;
temp.left = null;
temp.right = null;
return temp;
}
// Recursive Function to find height
// of binary tree
static int HeightOfTree(node root)
{
if (root == null)
return 0;
// Compute the height of each subtree
int lheight = HeightOfTree(root.left);
int rheight = HeightOfTree(root.right);
// Return the maximum of two
return Math.max(lheight + 1, rheight + 1);
}
// Function to Print nodes from right to left
static void Print_Level_Right_To_Left(node root, int level)
{
if (root == null)
return;
if (level == 1)
System.out.print(root.data + " ");
else if (level > 1)
{
Print_Level_Right_To_Left(root.right, level - 1);
Print_Level_Right_To_Left(root.left, level - 1);
}
}
// Function to Print nodes from left to right
static void Print_Level_Left_To_Right(node root, int level)
{
if (root == null)
return;
if (level == 1)
System.out.print(root.data + " ");
else if (level > 1)
{
Print_Level_Left_To_Right(root.left, level - 1);
Print_Level_Left_To_Right(root.right, level - 1);
}
}
// Function to print Reverse zigzag of
// a Binary tree
static void PrintReverseZigZag(node root)
{
// Flag is used to mark the change
// in level
int flag = 1;
// Height of tree
int height = HeightOfTree(root);
for (int i = height; i >= 1; i--)
{
// If flag value is one print nodes
// from right to left
if (flag == 1)
{
Print_Level_Right_To_Left(root, i);
// Mark flag as zero so that next time
// tree is traversed from left to right
flag = 0;
}
// If flag is zero print nodes
// from left to right
else if (flag == 0)
{
Print_Level_Left_To_Right(root, i);
// Mark flag as one so that next time
// nodes are printed from right to left
flag = 1;
}
}
}
// Driver code
public static void main(String[] args)
{
node root = newNode(5);
root.left = newNode(9);
root.right = newNode(3);
root.left.left = newNode(6);
root.right.right = newNode(4);
root.left.left.left = newNode(8);
root.left.left.right = newNode(7);
PrintReverseZigZag(root);
}
}
// This code is contributed by Prerna Saini.
Python3
# Python3 program to print reverse # zigzag order of binary tree # Binary tree node class Node: def __init__(self, data): self.data = data self.left = None self.right = None # Recursive Function to find # height of binary tree def HeightOfTree(root): if root == None: return 0 # Compute the height of each subtree lheight = HeightOfTree(root.left) rheight = HeightOfTree(root.right) # Return the maximum of two return max(lheight + 1, rheight + 1) # Function to Print nodes from right to left def Print_Level_Right_To_Left(root, level): if root == None: return if level == 1: print(root.data, end = " ") elif level > 1: Print_Level_Right_To_Left(root.right, level - 1) Print_Level_Right_To_Left(root.left, level - 1) # Function to Print nodes from left to right def Print_Level_Left_To_Right(root, level): if root == None: return if level == 1: print(root.data, end = " ") elif level > 1: Print_Level_Left_To_Right(root.left, level - 1) Print_Level_Left_To_Right(root.right, level - 1) # Function to print Reverse # zigzag of a Binary tree def PrintReverseZigZag(root): # Flag is used to mark the # change in level flag = 1 # Height of tree height = HeightOfTree(root) for i in range(height, 0, -1): # If flag value is one print # nodes from right to left if flag == 1: Print_Level_Right_To_Left(root, i) # Mark flag as zero so that next time # tree is traversed from left to right flag = 0 # If flag is zero print nodes # from left to right elif flag == 0: Print_Level_Left_To_Right(root, i) # Mark flag as one so that next time # nodes are printed from right to left flag = 1 # Driver code if __name__ == "__main__": root = Node(5) root.left = Node(9) root.right = Node(3) root.left.left = Node(6) root.right.right = Node(4) root.left.left.left = Node(8) root.left.left.right = Node(7) PrintReverseZigZag(root) # This code is contributed by Rituraj Jain
C#
// C# program to print reverse
// zigzag order of binary tree
using System;
class GfG
{
// Binary tree node
public class node
{
public node left;
public node right;
public int data;
}
// Function to create a new
// Binary node
static node newNode(int data)
{
node temp = new node();
temp.data = data;
temp.left = null;
temp.right = null;
return temp;
}
// Recursive Function to find height
// of binary tree
static int HeightOfTree(node root)
{
if (root == null)
return 0;
// Compute the height of each subtree
int lheight = HeightOfTree(root.left);
int rheight = HeightOfTree(root.right);
// Return the maximum of two
return Math.Max(lheight + 1, rheight + 1);
}
// Function to Print nodes from right to left
static void Print_Level_Right_To_Left(node root, int level)
{
if (root == null)
return;
if (level == 1)
Console.Write(root.data + " ");
else if (level > 1)
{
Print_Level_Right_To_Left(root.right, level - 1);
Print_Level_Right_To_Left(root.left, level - 1);
}
}
// Function to Print nodes from left to right
static void Print_Level_Left_To_Right(node root, int level)
{
if (root == null)
return;
if (level == 1)
Console.Write(root.data + " ");
else if (level > 1)
{
Print_Level_Left_To_Right(root.left, level - 1);
Print_Level_Left_To_Right(root.right, level - 1);
}
}
// Function to print Reverse zigzag of
// a Binary tree
static void PrintReverseZigZag(node root)
{
// Flag is used to mark the change
// in level
int flag = 1;
// Height of tree
int height = HeightOfTree(root);
for (int i = height; i >= 1; i--)
{
// If flag value is one print nodes
// from right to left
if (flag == 1)
{
Print_Level_Right_To_Left(root, i);
// Mark flag as zero so that next time
// tree is traversed from left to right
flag = 0;
}
// If flag is zero print nodes
// from left to right
else if (flag == 0)
{
Print_Level_Left_To_Right(root, i);
// Mark flag as one so that next time
// nodes are printed from right to left
flag = 1;
}
}
}
// Driver code
public static void Main(String[] args)
{
node root = newNode(5);
root.left = newNode(9);
root.right = newNode(3);
root.left.left = newNode(6);
root.right.right = newNode(4);
root.left.left.left = newNode(8);
root.left.left.right = newNode(7);
PrintReverseZigZag(root);
}
}
/* This code contributed by PrinciRaj1992 */
Javascript
<script>
// JavaScript program to print reverse
// zigzag order of binary tree
// Binary tree node
class node
{
constructor(data) {
this.left = null;
this.right = null;
this.data = data;
}
}
// Function to create a new
// Binary node
function newNode(data)
{
let temp = new node(data);
return temp;
}
// Recursive Function to find height
// of binary tree
function HeightOfTree(root)
{
if (root == null)
return 0;
// Compute the height of each subtree
let lheight = HeightOfTree(root.left);
let rheight = HeightOfTree(root.right);
// Return the maximum of two
return Math.max(lheight + 1, rheight + 1);
}
// Function to Print nodes from right to left
function Print_Level_Right_To_Left(root, level)
{
if (root == null)
return;
if (level == 1)
document.write(root.data + " ");
else if (level > 1)
{
Print_Level_Right_To_Left(root.right, level - 1);
Print_Level_Right_To_Left(root.left, level - 1);
}
}
// Function to Print nodes from left to right
function Print_Level_Left_To_Right(root, level)
{
if (root == null)
return;
if (level == 1)
document.write(root.data + " ");
else if (level > 1)
{
Print_Level_Left_To_Right(root.left, level - 1);
Print_Level_Left_To_Right(root.right, level - 1);
}
}
// Function to print Reverse zigzag of
// a Binary tree
function PrintReverseZigZag(root)
{
// Flag is used to mark the change
// in level
let flag = 1;
// Height of tree
let height = HeightOfTree(root);
for (let i = height; i >= 1; i--)
{
// If flag value is one print nodes
// from right to left
if (flag == 1)
{
Print_Level_Right_To_Left(root, i);
// Mark flag as zero so that next time
// tree is traversed from left to right
flag = 0;
}
// If flag is zero print nodes
// from left to right
else if (flag == 0)
{
Print_Level_Left_To_Right(root, i);
// Mark flag as one so that next time
// nodes are printed from right to left
flag = 1;
}
}
}
let root = newNode(5);
root.left = newNode(9);
root.right = newNode(3);
root.left.left = newNode(6);
root.right.right = newNode(4);
root.left.left.left = newNode(8);
root.left.left.right = newNode(7);
PrintReverseZigZag(root);
</script>
Producción:
7 8 6 4 3 9 5
Complejidad de tiempo : O (N ^ 2), donde N es el número de Nodes en un árbol binario.
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por Sakshi_Srivastava y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA