Ruta palindrómica lexicográficamente más pequeña en un árbol binario

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

  1. La idea principal es usar Preorder Traversal
  2. Atraviesa el árbol en modo Preorder.
  3. Siga almacenando los valores de los Nodes en una string.
  4. 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 .
  5. Si es un palíndromo, guárdelo en una variable solo si lexicográficamente es el camino palindrómico más pequeño .
  6. 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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *