Dado un árbol binario , la tarea es imprimir todos los niveles palindrómicos de este árbol.
Nivel palíndromo Cualquier nivel de un árbol binario se dice que es un nivel palindrómico si al atravesarlo de izquierda a derecha, el resultado es el mismo que atravesar ese nivel de derecha a izquierda.
Ejemplos:
Input:
1
/ \
12 13
/ / \
11 6 11
\ /
2 2
Output:
1
11 6 11
2 2
Explanation:
First, third and fourth levels are palindrome.
Input:
7
/ \
22 22
/ \ \
3 6 3
/ \ \ /
1 5 8 1
/
23
Output:
7
22 22
3 6 3
23
Explanation:
First, second, third and fifth levels are palindrome.
Enfoque: para verificar si cada nivel es un nivel palindrómico, primero debemos hacer el recorrido de orden de nivel del árbol binario para obtener los valores en cada nivel. Luego, para cada nivel, verifique si es un palíndromo o no.
Aquí se utiliza una estructura de datos de cola para almacenar los niveles del árbol mientras se realiza el recorrido de orden de nivel.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for printing a
// Palindromic Levels of Binary Tree
#include <bits/stdc++.h>
using namespace std;
// A Tree node
struct Node {
int key;
struct Node *left, *right;
};
// Utility function to create a new node
Node* newNode(int key)
{
Node* temp = new Node;
temp->key = key;
temp->left = temp->right = NULL;
return (temp);
}
// Function to print a Palindromic level
void printLevel(struct Node* queue[],
int index, int size)
{
for (int i = index; i < size; i++) {
cout << queue[i]->key << " ";
}
cout << endl;
}
// Function to check whether given level
// is Palindromic level or not
bool isPalindrome(struct Node* queue[],
int index, int size)
{
while (index < size) {
// check value of two nodes are
// equal or not
if (queue[index++]->key
!= queue[size--]->key)
return false;
}
return true;
}
// Utility function to get palindromic
// level of a given Binary tree
void printPalLevel(struct Node* node,
struct Node* queue[],
int index, int size)
{
// Print root node value
// as a single value in a
// level is also a Palindrome
cout << queue[index]->key << endl;
// Level order traversal of Tree
while (index < size) {
int curr_size = size;
while (index < curr_size) {
struct Node* temp = queue[index];
if (temp->left != NULL) {
queue[size++] = temp->left;
}
if (temp->right != NULL) {
queue[size++] = temp->right;
}
index++;
}
// Check if level is Palindrome or not
if (isPalindrome(queue, index, size - 1)) {
printLevel(queue, index, size);
}
}
}
// Function to find total no of nodes
int findSize(struct Node* node)
{
if (node == NULL)
return 0;
return 1
+ findSize(node->left)
+ findSize(node->right);
}
// Function to find palindromic level
// In a given binary tree
void printPalindromicLevel(struct Node* node)
{
int t_size = findSize(node);
struct Node* queue[t_size];
queue[0] = node;
printPalLevel(node, queue, 0, 1);
}
// Driver Code
int main()
{
/* 10
/ \
13 13
/ \
14 15
/ \ / \
21 22 22 21
/
8 */
// Create Binary Tree as shown
Node* root = newNode(10);
root->left = newNode(13);
root->right = newNode(13);
root->right->left = newNode(14);
root->right->right = newNode(15);
root->right->left->left = newNode(21);
root->right->left->right = newNode(22);
root->right->right->left = newNode(22);
root->right->right->right = newNode(21);
root->right->right->right->left = newNode(8);
// Print Palindromic Levels
printPalindromicLevel(root);
return 0;
}
Java
// Java program for printing a
// Palindromic Levels of Binary Tree
class GFG{
// A Tree node
static class Node {
int key;
Node left, right;
};
// Utility function to create a new node
static Node newNode(int key)
{
Node temp = new Node();
temp.key = key;
temp.left = temp.right = null;
return (temp);
}
// Function to print a Palindromic level
static void printLevel(Node queue[],
int index, int size)
{
for (int i = index; i < size; i++) {
System.out.print(queue[i].key+ " ");
}
System.out.println();
}
// Function to check whether given level
// is Palindromic level or not
static boolean isPalindrome(Node queue[],
int index, int size)
{
while (index < size) {
// check value of two nodes are
// equal or not
if (queue[index++].key
!= queue[size--].key)
return false;
}
return true;
}
// Utility function to get palindromic
// level of a given Binary tree
static void printPalLevel(Node node,
Node queue[],
int index, int size)
{
// Print root node value
// as a single value in a
// level is also a Palindrome
System.out.print(queue[index].key +"\n");
// Level order traversal of Tree
while (index < size) {
int curr_size = size;
while (index < curr_size) {
Node temp = queue[index];
if (temp.left != null) {
queue[size++] = temp.left;
}
if (temp.right != null) {
queue[size++] = temp.right;
}
index++;
}
// Check if level is Palindrome or not
if (isPalindrome(queue, index, size - 1)) {
printLevel(queue, index, size);
}
}
}
// Function to find total no of nodes
static int findSize(Node node)
{
if (node == null)
return 0;
return 1
+ findSize(node.left)
+ findSize(node.right);
}
// Function to find palindromic level
// In a given binary tree
static void printPalindromicLevel(Node node)
{
int t_size = findSize(node);
Node []queue = new Node[t_size];
queue[0] = node;
printPalLevel(node, queue, 0, 1);
}
// Driver Code
public static void main(String[] args)
{
/* 10
/ \
13 13
/ \
14 15
/ \ / \
21 22 22 21
/
8 */
// Create Binary Tree as shown
Node root = newNode(10);
root.left = newNode(13);
root.right = newNode(13);
root.right.left = newNode(14);
root.right.right = newNode(15);
root.right.left.left = newNode(21);
root.right.left.right = newNode(22);
root.right.right.left = newNode(22);
root.right.right.right = newNode(21);
root.right.right.right.left = newNode(8);
// Print Palindromic Levels
printPalindromicLevel(root);
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program for printing a # Palindromic Levels of Binary Tree # A BST node class Node: def __init__(self, x): self.key = x self.left = None self.right = None # Function to pra Palindromic level def printLevel(queue, index, size): for i in range(index, size): print(queue[i].key, end = " ") print() # Function to check whether given level # is Palindromic level or not def isPalindrome(queue, index, size): #print(index,size) while (index < size): # Check value of two nodes are # equal or not if (queue[index].key != queue[size].key): return False index += 1 size -= 1 return True # Utility function to get palindromic # level of a given Binary tree def printPalLevel(node, queue, index, size): # Print root node value # as a single value in a # level is also a Palindrome print(queue[index].key) # Level order traversal of Tree while (index < size): curr_size = size while (index < curr_size): temp = queue[index] if (temp.left != None): queue[size] = temp.left size += 1 if (temp.right != None): queue[size] = temp.right size += 1 index += 1 # Check if level is Palindrome or not if (isPalindrome(queue, index, size - 1) == True): printLevel(queue, index, size) # Function to find total no of nodes def findSize(node): if (node == None): return 0 return (1 + findSize(node.left) + findSize(node.right)) # Function to find palindromic level # In a given binary tree def printPalindromicLevel(node): t_size = findSize(node) queue = [None for i in range(t_size)] queue[0] = node printPalLevel(node, queue, 0, 1) # Driver Code if __name__ == '__main__': # 10 # / \ # 13 13 # / \ # 14 15 # / \ / \ # 21 22 22 21 # / # 8 # Create Binary Tree as shown root = Node(10) root.left = Node(13) root.right = Node(13) root.right.left = Node(14) root.right.right = Node(15) root.right.left.left = Node(21) root.right.left.right = Node(22) root.right.right.left = Node(22) root.right.right.right = Node(21) root.right.right.right.left = Node(8) # Print Palindromic Levels printPalindromicLevel(root) # This code is contributed by mohit kumar 29
C#
// C# program for printing a
// Palindromic Levels of Binary Tree
using System;
class GFG{
// A Tree node
class Node {
public int key;
public Node left, right;
};
// Utility function to create a new node
static Node newNode(int key)
{
Node temp = new Node();
temp.key = key;
temp.left = temp.right = null;
return (temp);
}
// Function to print a Palindromic level
static void printLevel(Node []queue,
int index, int size)
{
for (int i = index; i < size; i++) {
Console.Write(queue[i].key+ " ");
}
Console.WriteLine();
}
// Function to check whether given level
// is Palindromic level or not
static bool isPalindrome(Node []queue,
int index, int size)
{
while (index < size) {
// check value of two nodes are
// equal or not
if (queue[index++].key
!= queue[size--].key)
return false;
}
return true;
}
// Utility function to get palindromic
// level of a given Binary tree
static void printPalLevel(Node node,
Node []queue,
int index, int size)
{
// Print root node value
// as a single value in a
// level is also a Palindrome
Console.Write(queue[index].key +"\n");
// Level order traversal of Tree
while (index < size) {
int curr_size = size;
while (index < curr_size) {
Node temp = queue[index];
if (temp.left != null) {
queue[size++] = temp.left;
}
if (temp.right != null) {
queue[size++] = temp.right;
}
index++;
}
// Check if level is Palindrome or not
if (isPalindrome(queue, index, size - 1)) {
printLevel(queue, index, size);
}
}
}
// Function to find total no of nodes
static int findSize(Node node)
{
if (node == null)
return 0;
return 1
+ findSize(node.left)
+ findSize(node.right);
}
// Function to find palindromic level
// In a given binary tree
static void printPalindromicLevel(Node node)
{
int t_size = findSize(node);
Node []queue = new Node[t_size];
queue[0] = node;
printPalLevel(node, queue, 0, 1);
}
// Driver Code
public static void Main(String[] args)
{
/* 10
/ \
13 13
/ \
14 15
/ \ / \
21 22 22 21
/
8 */
// Create Binary Tree as shown
Node root = newNode(10);
root.left = newNode(13);
root.right = newNode(13);
root.right.left = newNode(14);
root.right.right = newNode(15);
root.right.left.left = newNode(21);
root.right.left.right = newNode(22);
root.right.right.left = newNode(22);
root.right.right.right = newNode(21);
root.right.right.right.left = newNode(8);
// Print Palindromic Levels
printPalindromicLevel(root);
}
}
// This code is contributed by sapnasingh4991
Javascript
<script>
// Javascript program for printing a
// Palindromic Levels of Binary Tree
// A Tree node
class Node
{
// Utility function to create
// a new node
constructor(key)
{
this.key = key;
this.left = this.right = null;
}
}
// Function to print a Palindromic level
function printLevel(queue, index, size)
{
for(let i = index; i < size; i++)
{
document.write(queue[i].key + " ");
}
document.write("<br>");
}
// Function to check whether given level
// is Palindromic level or not
function isPalindrome(queue, index, size)
{
while (index < size)
{
// Check value of two nodes are
// equal or not
if (queue[index++].key !=
queue[size--].key)
return false;
}
return true;
}
// Utility function to get palindromic
// level of a given Binary tree
function printPalLevel(node, queue,
index, size)
{
// Print root node value
// as a single value in a
// level is also a Palindrome
document.write(queue[index].key + "<br>");
// Level order traversal of Tree
while (index < size)
{
let curr_size = size;
while (index < curr_size)
{
let temp = queue[index];
if (temp.left != null)
{
queue[size++] = temp.left;
}
if (temp.right != null)
{
queue[size++] = temp.right;
}
index++;
}
// Check if level is Palindrome or not
if (isPalindrome(queue, index, size - 1))
{
printLevel(queue, index, size);
}
}
}
// Function to find total no of nodes
function findSize(node)
{
if (node == null)
return 0;
return 1 + findSize(node.left) +
findSize(node.right);
}
// Function to find palindromic level
// In a given binary tree
function printPalindromicLevel(node)
{
let t_size = findSize(node);
let queue = new Array(t_size);
queue[0] = node;
printPalLevel(node, queue, 0, 1);
}
// Driver Code
/* 10
/ \
13 13
/ \
14 15
/ \ / \
21 22 22 21
/
8 */
// Create Binary Tree as shown
let root = new Node(10);
root.left = new Node(13);
root.right = new Node(13);
root.right.left = new Node(14);
root.right.right = new Node(15);
root.right.left.left = new Node(21);
root.right.left.right = new Node(22);
root.right.right.left = new Node(22);
root.right.right.right = new Node(21);
root.right.right.right.left = new Node(8);
// Print Palindromic Levels
printPalindromicLevel(root);
// This code is contributed by unknown2108
</script>
Producción:
10 13 13 21 22 22 21 8
Publicación traducida automáticamente
Artículo escrito por MohammadMudassir y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA