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>
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