Dado un árbol binario que consta de N Nodes, la tarea es verificar si los Nodes en la vista superior de un árbol binario forman un número de palíndromo o no. Si se encuentra que es un palíndromo, escriba «Sí» . De lo contrario, escriba “No” .
Ejemplos:
Entrada:
5
/ \
3 3
/ \ \
6 2 6
Salida: Sí
Explicación:
Los Nodes en la vista superior son {6, 3, 5, 3, 6}. Por tanto, el número generado ( = 63536) es un palíndromo.Entrada:
1
/ \
4 2
Salida: No
Enfoque: para resolver el problema dado, la idea es encontrar la vista superior del árbol binario dado usando el enfoque discutido en este artículo y almacenarlo en una array, digamos arr[] . Ahora, compruebe si la array arr[] es palíndromo o no . Si es cierto, escriba Sí , de lo contrario , escriba No.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Structure of the node
// of a Binary Tree
struct Node {
Node* left;
Node* right;
int hd;
int data;
};
// Function to create a new node
Node* newNode(int key)
{
Node* node = new Node();
node->left = node->right = NULL;
node->data = key;
return node;
}
// Function to check if array
// is a palindrome or not
void isPalindrome(vector<int> arr)
{
// Store the size of arr[]
int n = arr.size();
// Initialise flag to 0
int flag = 0;
// Iterate till half the array length
for (int i = 0; i <= n / 2
&& n != 0;
i++) {
// If the first and last
// array elements are different
if (arr[i] != arr[n - i - 1]) {
flag = 1;
break;
}
}
// If flag is set, then print No
if (flag == 1)
cout << "No";
else
cout << "Yes";
}
// Function to find the top view
// of the given Binary Tree
void topview(Node* root)
{
// Base Case
if (root == NULL)
return;
// Stores the nodes while
// performing tree traversal
queue<Node*> q;
map<int, int> m;
int hd = 0;
root->hd = hd;
// Push node and horizontal
// distance into the queue
q.push(root);
while (q.size()) {
hd = root->hd;
if (m.count(hd) == 0)
m[hd] = root->data;
// If root's left child exists
if (root->left) {
root->left->hd = hd - 1;
q.push(root->left);
}
// If root's right child exists
if (root->right) {
root->right->hd = hd + 1;
q.push(root->right);
}
q.pop();
root = q.front();
}
// Store the top view in a vector
vector<int> v;
// Traverse the map
for (auto i = m.begin();
i != m.end(); i++) {
// Insert the element in v
v.push_back(i->second);
}
// Function call to check if
// vector v is palindromic or not
isPalindrome(v);
}
// Driver Code
int main()
{
// Binary Tree Formation
Node* root = newNode(5);
root->left = newNode(3);
root->right = newNode(3);
root->left->left = newNode(6);
root->left->right = newNode(2);
root->right->right = newNode(6);
topview(root);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Structure of the node
// of a Binary Tree
static class Node
{
Node left;
Node right;
int hd;
int data;
};
// Function to create a new node
static Node newNode(int key)
{
Node node = new Node();
node.left = node.right = null;
node.data = key;
return node;
}
// Function to check if array
// is a palindrome or not
static void isPalindrome(Vector<Integer> arr)
{
// Store the size of arr[]
int n = arr.size();
// Initialise flag to 0
int flag = 0;
// Iterate till half the array length
for(int i = 0; i <= n / 2 && n != 0; i++)
{
// If the first and last
// array elements are different
if (arr.get(i) != arr.get(n - i - 1))
{
flag = 1;
break;
}
}
// If flag is set, then print No
if (flag == 1)
System.out.print("No");
else
System.out.print("Yes");
}
// Function to find the top view
// of the given Binary Tree
static void topview(Node root)
{
// Base Case
if (root == null)
return;
// Stores the nodes while
// performing tree traversal
Queue<Node> q = new LinkedList<>();
HashMap<Integer, Integer> m = new HashMap<>();
int hd = 0;
root.hd = hd;
// Push node and horizontal
// distance into the queue
q.add(root);
while (q.size() > 0)
{
hd = root.hd;
if (m.containsKey(hd) && m.get(hd) == 0)
m.put(hd, root.data);
// If root's left child exists
if (root.left != null)
{
root.left.hd = hd - 1;
q.add(root.left);
}
// If root's right child exists
if (root.right != null)
{
root.right.hd = hd + 1;
q.add(root.right);
}
q.remove();
root = q.peek();
}
// Store the top view in a vector
Vector<Integer> v = new Vector<Integer>();
// Traverse the map
for(Map.Entry<Integer,Integer> i : m.entrySet())
{
// Insert the element in v
v.add(i.getValue());
}
// Function call to check if
// vector v is palindromic or not
isPalindrome(v);
}
// Driver Code
public static void main(String[] args)
{
// Binary Tree Formation
Node root = newNode(5);
root.left = newNode(3);
root.right = newNode(3);
root.left.left = newNode(6);
root.left.right = newNode(2);
root.right.right = newNode(6);
topview(root);
}
}
// This code is contributed by shikhasingrajput
Python3
# Python3 program for the above approach
# Structure of the node
# of a Binary Tree
class newNode:
# Construct to create a newNode
def __init__(self, key):
self.data = key
self.left = None
self.right = None
self.hd = 0
# Function to check if array
# is a palindrome or not
def isPalindrome(arr):
# Store the size of arr[]
n = len(arr)
# Initialise flag to 0
flag = 0
# Iterate till half the array length
i = 0
while i <= n // 2 and n != 0:
# If the first and last
# array elements are different
if (arr[i] != arr[n - i - 1]):
flag = 1
break
i += 1
# If flag is set, then print No
if (flag == 1):
print("No")
else:
print("Yes")
# Function to find the top view
# of the given Binary Tree
def topview(root):
# Base case
if(root == None) :
return
q = []
m = dict()
hd = 0
root.hd = hd
# push node and horizontal
# distance to queue
q.append(root)
while(len(q)) :
root = q[0]
hd = root.hd
# count function returns 1 if the
# container contains an element
# whose key is equivalent to hd,
# or returns zero otherwise.
if hd not in m:
m[hd] = root.data
if(root.left) :
root.left.hd = hd - 1
q.append(root.left)
if(root.right):
root.right.hd = hd + 1
q.append(root.right)
q.pop(0)
v = []
# Traverse the map
for i in sorted(m):
# Insert the element in v
v.append(m[i])
# Function call to check if
# vector v is palindromic or not
isPalindrome(v)
# Driver Code
# Binary Tree Formation
root = newNode(5)
root.left = newNode(3)
root.right = newNode(3)
root.left.left = newNode(6)
root.left.right = newNode(2)
root.right.right = newNode(6)
topview(root)
# This code is contributed by rohitsingh07052.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG{
// Structure of the node
// of a Binary Tree
class Node
{
public Node left;
public Node right;
public int hd;
public int data;
};
// Function to create a new node
static Node newNode(int key)
{
Node node = new Node();
node.left = node.right = null;
node.data = key;
return node;
}
// Function to check if array
// is a palindrome or not
static void isPalindrome(List<int> arr)
{
// Store the size of []arr
int n = arr.Count;
// Initialise flag to 0
int flag = 0;
// Iterate till half the array length
for(int i = 0; i <= n / 2 && n != 0; i++)
{
// If the first and last
// array elements are different
if (arr[i] != arr[n - i - 1])
{
flag = 1;
break;
}
}
// If flag is set, then print No
if (flag == 1)
Console.Write("No");
else
Console.Write("Yes");
}
// Function to find the top view
// of the given Binary Tree
static void topview(Node root)
{
// Base Case
if (root == null)
return;
// Stores the nodes while
// performing tree traversal
Queue<Node> q = new Queue<Node>();
Dictionary<int, int> m = new Dictionary<int, int>();
int hd = 0;
root.hd = hd;
// Push node and horizontal
// distance into the queue
q.Enqueue(root);
while (q.Count > 0)
{
hd = root.hd;
if (m.ContainsKey(hd) && m[hd] == 0)
m[hd] = root.data;
// If root's left child exists
if (root.left != null)
{
root.left.hd = hd - 1;
q.Enqueue(root.left);
}
// If root's right child exists
if (root.right != null)
{
root.right.hd = hd + 1;
q.Enqueue(root.right);
}
root = q.Peek();
q.Dequeue();
}
// Store the top view in a vector
List<int> v = new List<int>();
// Traverse the map
foreach(KeyValuePair<int,int> i in m)
{
// Insert the element in v
v.Add(i.Value);
}
// Function call to check if
// vector v is palindromic or not
isPalindrome(v);
}
// Driver Code
public static void Main(String[] args)
{
// Binary Tree Formation
Node root = newNode(5);
root.left = newNode(3);
root.right = newNode(3);
root.left.left = newNode(6);
root.left.right = newNode(2);
root.right.right = newNode(6);
topview(root);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript program for the above approach
class Node
{
constructor(key) {
this.left = null;
this.right = null;
this.data = key;
}
}
// Function to create a new node
function newNode(key)
{
let node = new Node(key);
return node;
}
// Function to check if array
// is a palindrome or not
function isPalindrome(arr)
{
// Store the size of arr[]
let n = arr.length;
// Initialise flag to 0
let flag = 0;
// Iterate till half the array length
for(let i = 0; i <= parseInt(n / 2, 10) && n != 0; i++)
{
// If the first and last
// array elements are different
if (arr[i] != arr[n - i - 1])
{
flag = 1;
break;
}
}
// If flag is set, then print No
if (flag == 1)
document.write("No");
else
document.write("Yes");
}
// Function to find the top view
// of the given Binary Tree
function topview(root)
{
// Base Case
if (root == null)
return;
// Stores the nodes while
// performing tree traversal
let q = [];
let m = new Map();
let hd = 0;
root.hd = hd;
// Push node and horizontal
// distance into the queue
q.push(root);
while (q.length > 0)
{
hd = root.hd;
if (m.has(hd) && m.get(hd) == 0)
m.set(hd, root.data);
// If root's left child exists
if (root.left != null)
{
root.left.hd = hd - 1;
q.push(root.left);
}
// If root's right child exists
if (root.right != null)
{
root.right.hd = hd + 1;
q.push(root.right);
}
q.shift();
root = q[0];
}
// Store the top view in a vector
let v = [];
// Traverse the map
m.forEach((values,keys)=>{
// Insert the element in v
v.push(values);
})
// Function call to check if
// vector v is palindromic or not
isPalindrome(v);
}
// Binary Tree Formation
let root = newNode(5);
root.left = newNode(3);
root.right = newNode(3);
root.left.left = newNode(6);
root.left.right = newNode(2);
root.right.right = newNode(6);
topview(root);
</script>
Producción:
Yes
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por rohitsingh07052 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA