Dado un árbol binario con cada Node representando un alfabeto, la tarea es encontrar lexicográficamente la ruta palindrómica más pequeña de raíz a hoja . Si no existe una ruta palindrómica, imprima «No existe una ruta palindrómica» .
Ejemplos:
Entrada:
a
/ \
c b
/ \ / \
a gb x
\
a
Salida:
abba
Explicación:
Había un total de 4 caminos de raíz a hoja, de los cuales 2 caminos (es decir, «aca» y «abba») eran caminos palindrómicos pero como » abba” es lexicográficamente más pequeño, imprima “abba” como salida.Entrada:
a
/ \
z k
/ \ / \
s ek u
\
e
Salida:
No existe ruta palindrómica
Enfoque: Siga los pasos para resolver el problema
- La idea principal es usar Preorder Traversal
- Atraviesa el árbol en modo Preorder.
- Siga almacenando los valores de los Nodes en una string.
- Tan pronto como se alcance un Node de hoja, verifique si la string formada desde una ruta de raíz a hoja es un palíndromo o no .
- Si es un palíndromo, guárdelo en una variable solo si lexicográficamente es el camino palindrómico más pequeño .
- Imprime el palíndromo, si existe.
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;
// Struct binary tree node
struct Node {
char data;
Node *left, *right;
};
// Function to create a new node
Node* newNode(char data)
{
Node* temp = new Node();
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
// Function to check if the
// string is palindrome or not
bool checkPalindrome(string s)
{
int low = 0, high = (int)s.size() - 1;
while (low < high) {
if (s[low] != s[high])
return false;
low++;
high--;
}
return true;
}
// Function to find the lexicographically
// smallest palindromic path in the Binary Tree
void lexicographicallySmall(Node* root, string s,
string& finalAns)
{
// Base case
if (root == NULL)
return;
// Append current node's
// data to the string
s += root->data;
// Check if a node is leaf or not
if (!root->left and !root->right) {
if (checkPalindrome(s)) {
// Check for the 1st
// Palindromic Path
if (finalAns == "$")
finalAns = s;
// Store lexicographically the
// smallest palindromic path
else
finalAns = min(finalAns, s);
}
return;
}
// Recursively traverse left subtree
lexicographicallySmall(root->left,
s, finalAns);
// Recursively traverse right subtree
lexicographicallySmall(root->right,
s, finalAns);
}
// Function to get smallest
// lexicographical palindromic
// path
void getPalindromePath(Node* root)
{
// Variable which stores
// the final result
string finalAns = "$";
// Function call to compute
// lexicographically smallest
// palindromic Path
lexicographicallySmall(root, "",
finalAns);
if (finalAns == "$")
cout << "No Palindromic Path exists";
else
cout << finalAns;
}
// Driver Code
int main()
{
// Construct binary tree
Node* root = newNode('a');
root->left = newNode('c');
root->left->left = newNode('a');
root->left->right = newNode('g');
root->right = newNode('b');
root->right->left = newNode('b');
root->right->right = newNode('x');
root->right->left->right = newNode('a');
getPalindromePath(root);
return 0;
}
Java
// Java program
// for the above approach
import java.util.*;
class GFG
{
static String finalAns="";
// Struct binary tree node
static class Node
{
char data;
Node left, right;
};
// Function to create a new node
static Node newNode(char data)
{
Node temp = new Node();
temp.data = data;
temp.left = temp.right = null;
return temp;
}
// Function to check if the
// String is palindrome or not
static boolean checkPalindrome(String s)
{
int low = 0, high = (int)s.length() - 1;
while (low < high)
{
if (s.charAt(low) != s.charAt(high))
return false;
low++;
high--;
}
return true;
}
// Function to find the lexicographically
// smallest palindromic path in the Binary Tree
static void lexicographicallySmall(Node root, String s)
{
// Base case
if (root == null)
return;
// Append current node's
// data to the String
s += root.data;
// Check if a node is leaf or not
if (root.left == null && root.right == null)
{
if (checkPalindrome(s))
{
// Check for the 1st
// Palindromic Path
if (finalAns == "$")
finalAns = s;
// Store lexicographically the
// smallest palindromic path
else
finalAns = finalAns.compareTo(s) <= 0 ? finalAns:s;
}
return;
}
// Recursively traverse left subtree
lexicographicallySmall(root.left,
s);
// Recursively traverse right subtree
lexicographicallySmall(root.right,
s);
}
// Function to get smallest
// lexicographical palindromic
// path
static void getPalindromePath(Node root)
{
// Variable which stores
// the final result
finalAns = "$";
// Function call to compute
// lexicographically smallest
// palindromic Path
lexicographicallySmall(root, "");
if (finalAns == "$")
System.out.print("No Palindromic Path exists");
else
System.out.print(finalAns);
}
// Driver Code
public static void main(String[] args)
{
// Construct binary tree
Node root = newNode('a');
root.left = newNode('c');
root.left.left = newNode('a');
root.left.right = newNode('g');
root.right = newNode('b');
root.right.left = newNode('b');
root.right.right = newNode('x');
root.right.left.right = newNode('a');
getPalindromePath(root);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program
# for the above approach
# Struct binary tree node
class Node:
def __init__(self, d):
self.data = d
self.left = None
self.right = None
# Function to check if the
# is palindrome or not
def checkPalindrome(s):
low, high = 0, len(s) - 1
while (low < high):
if (s[low] != s[high]):
return False
low += 1
high -= 1
return True
# Function to find the lexicographically
# smallest palindromic path in the Binary Tree
def lexicographicallySmall(root, s):
global finalAns
# Base case
if (root == None):
return
# Append current node's
# data to the string
s += root.data
# Check if a node is leaf or not
if (not root.left and not root.right):
if (checkPalindrome(s)):
# Check for the 1st
# Palindromic Path
if (finalAns == "$"):
finalAns = s
# Store lexicographically the
# smallest palindromic path
else:
finalAns = min(finalAns, s)
return
# Recursively traverse left subtree
lexicographicallySmall(root.left, s)
# Recursively traverse right subtree
lexicographicallySmall(root.right, s)
# Function to get smallest
# lexicographical palindromic
# path
def getPalindromePath(root):
global finalAns
# Variable which stores
# the final result
finalAns = "$"
# Function call to compute
# lexicographically smallest
# palindromic Path
lexicographicallySmall(root, "")
if (finalAns == "$"):
print("No Palindromic Path exists")
else:
print(finalAns)
# Driver Code
if __name__ == '__main__':
finalAns = ""
# Construct binary tree
root = Node('a')
root.left = Node('c')
root.left.left = Node('a')
root.left.right = Node('g')
root.right = Node('b')
root.right.left = Node('b')
root.right.right = Node('x')
root.right.left.right = Node('a')
getPalindromePath(root)
# This code is contributed by mohit kumar 29.
C#
// C# program
// for the above approach
using System;
public class GFG
{
static String finalAns = "";
// Struct binary tree node
class Node
{
public char data;
public Node left, right;
};
// Function to create a new node
static Node newNode(char data)
{
Node temp = new Node();
temp.data = data;
temp.left = temp.right = null;
return temp;
}
// Function to check if the
// String is palindrome or not
static bool checkPalindrome(String s)
{
int low = 0, high = (int)s.Length - 1;
while (low < high)
{
if (s[low] != s[high])
return false;
low++;
high--;
}
return true;
}
// Function to find the lexicographically
// smallest palindromic path in the Binary Tree
static void lexicographicallySmall(Node root, String s)
{
// Base case
if (root == null)
return;
// Append current node's
// data to the String
s += root.data;
// Check if a node is leaf or not
if (root.left == null && root.right == null)
{
if (checkPalindrome(s))
{
// Check for the 1st
// Palindromic Path
if (finalAns == "$")
finalAns = s;
// Store lexicographically the
// smallest palindromic path
else
finalAns = finalAns.CompareTo(s) <= 0 ? finalAns:s;
}
return;
}
// Recursively traverse left subtree
lexicographicallySmall(root.left,
s);
// Recursively traverse right subtree
lexicographicallySmall(root.right,
s);
}
// Function to get smallest
// lexicographical palindromic
// path
static void getPalindromePath(Node root)
{
// Variable which stores
// the readonly result
finalAns = "$";
// Function call to compute
// lexicographically smallest
// palindromic Path
lexicographicallySmall(root, "");
if (finalAns == "$")
Console.Write("No Palindromic Path exists");
else
Console.Write(finalAns);
}
// Driver Code
public static void Main(String[] args)
{
// Construct binary tree
Node root = newNode('a');
root.left = newNode('c');
root.left.left = newNode('a');
root.left.right = newNode('g');
root.right = newNode('b');
root.right.left = newNode('b');
root.right.right = newNode('x');
root.right.left.right = newNode('a');
getPalindromePath(root);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program for the above approach
let finalAns="";
// Struct binary tree node
class Node
{
constructor(data) {
this.left = null;
this.right = null;
this.data = data;
}
}
// Function to create a new node
function newNode(data)
{
let temp = new Node(data);
return temp;
}
// Function to check if the
// String is palindrome or not
function checkPalindrome(s)
{
let low = 0, high = s.length - 1;
while (low < high)
{
if (s[low] != s[high])
return false;
low++;
high--;
}
return true;
}
// Function to find the lexicographically
// smallest palindromic path in the Binary Tree
function lexicographicallySmall(root, s)
{
// Base case
if (root == null)
return;
// Append current node's
// data to the String
s += root.data;
// Check if a node is leaf or not
if (root.left == null && root.right == null)
{
if (checkPalindrome(s))
{
// Check for the 1st
// Palindromic Path
if (finalAns == "$")
finalAns = s;
// Store lexicographically the
// smallest palindromic path
else
finalAns = finalAns.localeCompare(s) <= 0 ? finalAns:s;
}
return;
}
// Recursively traverse left subtree
lexicographicallySmall(root.left, s);
// Recursively traverse right subtree
lexicographicallySmall(root.right, s);
}
// Function to get smallest
// lexicographical palindromic
// path
function getPalindromePath(root)
{
// Variable which stores
// the final result
finalAns = "$";
// Function call to compute
// lexicographically smallest
// palindromic Path
lexicographicallySmall(root, "");
if (finalAns == "$")
document.write("No Palindromic Path exists");
else
document.write(finalAns);
}
// Construct binary tree
let root = newNode('a');
root.left = newNode('c');
root.left.left = newNode('a');
root.left.right = newNode('g');
root.right = newNode('b');
root.right.left = newNode('b');
root.right.right = newNode('x');
root.right.left.right = newNode('a');
getPalindromePath(root);
// This code is contributed by suresh07.
</script>
Producción:
abba
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N 2 )
Publicación traducida automáticamente
Artículo escrito por chirags_30 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA