Dada la raíz del árbol binario T y una lista enlazada L , la tarea es encontrar la dirección de la ruta seguida desde la raíz tal que exista una ruta desde la raíz a cualquier Node hoja del árbol tal que los valores sean que la ruta forma el enlace. Lista. Si no existe tal ruta, imprima «-1» .
Nota: El camino tomado en la dirección izquierda se denota por L y el camino tomado en la dirección derecha es R .
Ejemplos :
Entrada: LL = 1 -> 2 -> 5 -> 8
1
/ \
2 3
/ \ / \
4 5 6 8
/
8
Salida: LRL
Explicación:
La ruta de la lista enlazada en el árbol binario es la siguiente:
1
/ \
2 3
/ \ / \
4 5 6 8
/
8Entrada: LL = 1 -> 2 -> 4
1
/ \
2 2
/ \ / \
4 5 6 8
/
8
Salida: {L, L}
Enfoque: el problema dado se puede resolver recorriendo el árbol binario y la lista vinculada simultáneamente, si el Node actual no coincide con el Node actual de la lista vinculada, entonces esa ruta es incorrecta. De lo contrario, verifique el otro orden para las rutas válidas. Siga los pasos a continuación para resolver el problema dado:
- Declare una función , diga findPath(root, head, path) y realice los siguientes pasos en esta función:
- Si la raíz es NULL o el valor de la raíz no es el mismo que el valor del Node de la cabeza, devuelva false .
- Si el Node raíz actual es el Node hoja y head es el último Node, devuelva true .
- Inserte el carácter ‘L’ en la ruta del vector [] y llame recursivamente al subárbol izquierdo como findPath (raíz->izquierda, cabeza->siguiente, ruta) y si el valor devuelto por esta función es verdadero , entonces existe una ruta y devolver verdadero de la función . De lo contrario, saque el último carácter del vector path[] .
- Inserte el carácter ‘R’ en la ruta del vector [] y llame recursivamente al subárbol derecho como findPath (raíz->derecha, cabeza->siguiente, ruta) y si el valor devuelto por esta función es verdadero , entonces existe una ruta y devolver verdadero de la función . De lo contrario, saque el último carácter del vector path[] .
- De lo contrario, devuelve false desde la función.
- Inicialice un vector, digamos ruta [] que almacena la dirección si se encuentra la Lista enlazada en el árbol binario dado.
- Llame a la función findPath(root, head, path) .
- Si el tamaño de la ruta del vector es 0 , imprima «-1» . De lo contrario, imprima la ruta almacenada en el vector ruta[] .
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 ListNode {
int data;
ListNode* next;
ListNode(int data)
{
this->data = data;
this->next = NULL;
}
};
struct TreeNode {
TreeNode* left;
TreeNode* right;
int val;
TreeNode(int x)
: left(NULL), right(NULL), val(x)
{
}
};
// Function to create the Linked list
ListNode* makeList(int arr[], int n)
{
ListNode* h = NULL;
ListNode* root;
for (int i = 0; i < n; i++) {
int data = arr[i];
ListNode* node = new ListNode(data);
if (h == NULL) {
h = node;
root = h;
}
else {
root->next = node;
root = node;
}
}
return h;
}
// utility function to build tree
// from its level order traversal
TreeNode* build_tree(int nodes[], int n)
{
TreeNode* root = new TreeNode(nodes[0]);
queue<TreeNode*> q;
bool is_left = true;
TreeNode* cur = NULL;
q.push(root);
for (int i = 1; i < n; i++) {
TreeNode* node = NULL;
if (nodes[i] != '#') {
node = new TreeNode(nodes[i]);
q.push(node);
}
if (is_left) {
cur = q.front();
q.pop();
cur->left = node;
is_left = false;
}
else {
cur->right = node;
is_left = true;
}
}
return root;
}
// Function to find path of linked list
// in binary tree, by traversing the
// tree in pre-order fashion
bool findPath(TreeNode* root, ListNode* head,
vector<char>& path)
{
// Base Case
if (root == NULL) {
return false;
}
// If current tree node is not same
// as the current LL Node, then
// return False
if (root->val != head->data)
return false;
// Complete the path of LL is traced
if (root->left == NULL
and root->right == NULL
and head->next == NULL) {
return true;
}
// First go to left
path.push_back('L');
// If path found in left subtree
if (findPath(root->left,
head->next, path))
return true;
// Pop L because valid path is
// not traced
path.pop_back();
// Go to right
path.push_back('R');
// If path found in right subtree
if (findPath(root->right,
head->next, path))
return true;
// Pop R because valid path
// is not traced
path.pop_back();
return false;
}
// Function to find the valid path
void find(TreeNode* root, ListNode* head)
{
vector<char> path;
// Function call to find the direction
// of the LL path
findPath(root, head, path);
// If there doesn't exists any
// such paths
if (path.size() == 0) {
cout << "-1";
return;
}
// Print the path
for (int i = 0;
i < path.size(); i++) {
cout << path[i] << " ";
}
}
// Driver Code
int main()
{
int tree[] = { 1, 2, 3, 4, 5, 6,
8, -1, -1, 8 };
TreeNode* root = build_tree(tree, 10);
int ll[] = { 1, 2, 5, 8 };
ListNode* head = makeList(ll, 4);
find(root, head);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
static class ListNode {
int data;
ListNode next;
ListNode(int data)
{
this.data = data;
this.next = null;
}
};
static class TreeNode {
TreeNode left;
TreeNode right;
int val;
TreeNode(int x){
left = null;
right = null;
val = x;
}
};
// Function to create the Linked list
static ListNode makeList(int arr[], int n)
{
ListNode h = null;
ListNode root = new ListNode(0);
for (int i = 0; i < n; i++) {
int data = arr[i];
ListNode node = new ListNode(data);
if (h == null) {
h = node;
root = h;
}
else {
root.next = node;
root = node;
}
}
return h;
}
// utility function to build tree
// from its level order traversal
static TreeNode build_tree(int nodes[], int n)
{
TreeNode root = new TreeNode(nodes[0]);
Queue<TreeNode> q = new LinkedList<>();
boolean is_left = true;
TreeNode cur = null;
q.add(root);
for (int i = 1; i < n; i++) {
TreeNode node = null;
if (nodes[i] != 0) {
node = new TreeNode(nodes[i]);
q.add(node);
}
if (is_left) {
cur = q.peek();
q.remove();
cur.left = node;
is_left = false;
}
else {
cur.right = node;
is_left = true;
}
}
return root;
}
// Function to find path of linked list
// in binary tree, by traversing the
// tree in pre-order fashion
static boolean findPath(TreeNode root, ListNode head,
Vector<Character> path)
{
// Base Case
if (root == null) {
return false;
}
// If current tree node is not same
// as the current LL Node, then
// return False
if (root.val != head.data)
return false;
// Complete the path of LL is traced
if (root.left == null
&& root.right == null
&& head.next == null) {
return true;
}
// First go to left
path.add('L');
// If path found in left subtree
if (findPath(root.left,
head.next, path))
return true;
// Pop L because valid path is
// not traced
path.remove(path.size()-1);
// Go to right
path.add('R');
// If path found in right subtree
if (findPath(root.right,
head.next, path))
return true;
// Pop R because valid path
// is not traced
path.remove(path.size()-1);
return false;
}
// Function to find the valid path
static void find(TreeNode root, ListNode head)
{
Vector<Character> path = new Vector<Character>();
// Function call to find the direction
// of the LL path
findPath(root, head, path);
// If there doesn't exists any
// such paths
if (path.size() == 0) {
System.out.print("-1");
return;
}
// Print the path
for (int i = 0;
i < path.size(); i++) {
System.out.print(path.get(i)+ " ");
}
}
// Driver Code
public static void main(String[] args)
{
int tree[] = { 1, 2, 3, 4, 5, 6,
8, -1, -1, 8 };
TreeNode root = build_tree(tree, 10);
int ll[] = { 1, 2, 5, 8 };
ListNode head = makeList(ll, 4);
find(root, head);
}
}
// This code is contributed by 29AjayKumar
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG{
class ListNode {
public int data;
public ListNode next;
public ListNode(int data)
{
this.data = data;
this.next = null;
}
};
class TreeNode {
public TreeNode left;
public TreeNode right;
public int val;
public TreeNode(int x){
left = null;
right = null;
val = x;
}
};
// Function to create the Linked list
static ListNode makeList(int []arr, int n)
{
ListNode h = null;
ListNode root = new ListNode(0);
for (int i = 0; i < n; i++) {
int data = arr[i];
ListNode node = new ListNode(data);
if (h == null) {
h = node;
root = h;
}
else {
root.next = node;
root = node;
}
}
return h;
}
// utility function to build tree
// from its level order traversal
static TreeNode build_tree(int []nodes, int n)
{
TreeNode root = new TreeNode(nodes[0]);
Queue<TreeNode> q = new Queue<TreeNode>();
bool is_left = true;
TreeNode cur = null;
q.Enqueue(root);
for (int i = 1; i < n; i++) {
TreeNode node = null;
if (nodes[i] != 0) {
node = new TreeNode(nodes[i]);
q.Enqueue(node);
}
if (is_left) {
cur = q.Peek();
q.Dequeue();
cur.left = node;
is_left = false;
}
else {
cur.right = node;
is_left = true;
}
}
return root;
}
// Function to find path of linked list
// in binary tree, by traversing the
// tree in pre-order fashion
static bool findPath(TreeNode root, ListNode head,
List<char> path)
{
// Base Case
if (root == null) {
return false;
}
// If current tree node is not same
// as the current LL Node, then
// return False
if (root.val != head.data)
return false;
// Complete the path of LL is traced
if (root.left == null
&& root.right == null
&& head.next == null) {
return true;
}
// First go to left
path.Add('L');
// If path found in left subtree
if (findPath(root.left,
head.next, path))
return true;
// Pop L because valid path is
// not traced
path.RemoveAt(path.Count-1);
// Go to right
path.Add('R');
// If path found in right subtree
if (findPath(root.right,
head.next, path))
return true;
// Pop R because valid path
// is not traced
path.RemoveAt(path.Count-1);
return false;
}
// Function to find the valid path
static void find(TreeNode root, ListNode head)
{
List<char> path = new List<char>();
// Function call to find the direction
// of the LL path
findPath(root, head, path);
// If there doesn't exists any
// such paths
if (path.Count == 0) {
Console.Write("-1");
return;
}
// Print the path
for (int i = 0;
i < path.Count; i++) {
Console.Write(path[i]+ " ");
}
}
// Driver Code
public static void Main(String[] args)
{
int []tree = { 1, 2, 3, 4, 5, 6,
8, -1, -1, 8 };
TreeNode root = build_tree(tree, 10);
int []ll = { 1, 2, 5, 8 };
ListNode head = makeList(ll, 4);
find(root, head);
}
}
// This code is contributed by 29AjayKumar
Producción:
L R L
Complejidad de tiempo: O (N + M), donde N es el número de Nodes en el árbol binario y M es la longitud de la lista enlazada .
Espacio Auxiliar: O(H), donde H es la altura del árbol binario .