Dada una raíz del árbol binario y la cabeza de la lista enlazada , la tarea es verificar si todos los elementos de la lista enlazada corresponden a una ruta descendente desde cualquier Node en el árbol binario dado.
Ejemplos:
Entrada: árbol en la imagen de abajo, lista = {3, 6, 8}
Salida: Sí
Explicación: Existe un camino hacia abajo en el árbol binario dado, que tiene todos los elementos de la lista enlazada en el mismo orden.Entrada: árbol en la imagen de abajo, lista = {1, 2, 5, 7}
Salida: Sí
Enfoque: El problema dado se puede resolver con la ayuda del DFS Traversal of the Binary tree . Durante el recorrido DFS, si algún Node del árbol binario es igual al encabezado de la lista vinculada , se puede llamar a una función recursiva isPathUntil() para verificar recursivamente si los otros elementos de la lista vinculada también existen como una ruta desde ese Node. . Si se ha recorrido la lista enlazada completa, existe una ruta requerida válida, por lo tanto, devuelve true . De lo contrario, devuelve falso . Siga los pasos a continuación para resolver el problema dado:
- Declare una función, diga isSubPathUtil(root, head) y realice los siguientes pasos en esta función :
- Si la raíz es NULL , devuelve false .
- Si el encabezado es NULL, devuelve verdadero.
- Si el valor del Node raíz actual es el mismo que el valor de la cabecera actual de LL, llame recursivamente a isSubPathUtil(raíz->izquierda, cabecera->siguiente) e isSubPathUtil(raíz->derecha, cabecera->siguiente) y si el valor devuelto por una de estas llamadas recursivas es verdadero, entonces devuelve verdadero. De lo contrario, devuelve falso .
- Declare una función, diga isSubPath(root, head) y realice los siguientes pasos en esta función:
- Si la raíz es NULL , devuelve false .
- Si el encabezado es NULL , devuelve verdadero.
- Si el valor del Node raíz actual es el mismo que el valor de la cabecera actual de LL, llame recursivamente a isSubPath(raíz->izquierda, cabecera->siguiente) e isSubPath(raíz->derecha, cabecera->siguiente) y si el valor devuelto por una de estas llamadas recursivas es verdadero, entonces devuelve verdadero. De lo contrario, devuelva la llamada de valor recursivamente para isSubPath(root->left, head) e isSubPath(root->right, head) .
- Después de los pasos anteriores, si el valor devuelto por la función isSubPath(root, head) es verdadero , imprima Sí . De lo contrario , imprima 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;
// Node of the Linked list
struct listNode {
int val;
struct listNode* next;
// Constructor
listNode(int data)
{
this->val = data;
next = NULL;
}
};
// Node of the Binary Search tree
struct treeNode {
int val;
treeNode* right;
treeNode* left;
// Constructor
treeNode(int data)
{
this->val = data;
this->left = NULL;
this->right = NULL;
}
};
// Recursive function to check if there
// exist a path from the node curTree
// having the LL from the node curList
bool isPathUtil(listNode* curList,
treeNode* curTree)
{
// If the complete linked list
// is traversed
if (curList == NULL)
return true;
// If the tree node doesnot exist
if (curTree == NULL)
return false;
if (curList->val == curTree->val) {
// Recursively calling for the
// next element
return isPathUtil(curList->next,
curTree->left)
|| isPathUtil(curList->next,
curTree->right);
}
else {
// If not found, return false
return false;
}
}
// Function to check if the linked list
// exist as a downward path in Binary tree
// using the DFS Traversal of the Tree
bool isPath(listNode* head, treeNode* root)
{
// If the current node of the
// tree is Null
if (root == NULL)
return false;
// If the complete linked list
// has been found
if (head == NULL)
return true;
// Stores if there exist the
// required path
bool isPossible = false;
if (root->val == head->val) {
// Recursively calling to
// check the next node of
// the linked list
isPossible = isPathUtil(
head->next, root->left)
|| isPathUtil(
head->next, root->right);
}
// Recursive calling for the next
// elements of the binary tree
return isPossible || isPath(head, root->left)
|| isPath(head, root->right);
}
// Driver Code
int main()
{
treeNode* root = new treeNode(1);
root->left = new treeNode(2);
root->right = new treeNode(3);
root->left->left = new treeNode(4);
root->left->right = new treeNode(5);
root->left->right->left = new treeNode(7);
root->right->right = new treeNode(6);
root->right->right->left = new treeNode(8);
root->right->right->right = new treeNode(9);
listNode* head = new listNode(3);
head->next = new listNode(6);
head->next->next = new listNode(8);
// Function Call
cout << (isPath(head, root) ? "Yes" : "No");
return 0;
}
Java
// Java program for the above approach
//include "bits/stdJava.h"
import java.util.*;
class GFG{
// Node of the Linked list
static class listNode {
int val;
listNode next;
// Constructor
listNode(int data)
{
this.val = data;
next = null;
}
};
// Node of the Binary Search tree
static class treeNode {
int val;
treeNode right;
treeNode left;
// Constructor
treeNode(int data)
{
this.val = data;
this.left = null;
this.right = null;
}
};
// Recursive function to check if there
// exist a path from the node curTree
// having the LL from the node curList
static boolean isPathUtil(listNode curList,
treeNode curTree)
{
// If the complete linked list
// is traversed
if (curList == null)
return true;
// If the tree node doesnot exist
if (curTree == null)
return false;
if (curList.val == curTree.val) {
// Recursively calling for the
// next element
return isPathUtil(curList.next,
curTree.left)
|| isPathUtil(curList.next,
curTree.right);
}
else {
// If not found, return false
return false;
}
}
// Function to check if the linked list
// exist as a downward path in Binary tree
// using the DFS Traversal of the Tree
static boolean isPath(listNode head, treeNode root)
{
// If the current node of the
// tree is Null
if (root == null)
return false;
// If the complete linked list
// has been found
if (head == null)
return true;
// Stores if there exist the
// required path
boolean isPossible = false;
if (root.val == head.val) {
// Recursively calling to
// check the next node of
// the linked list
isPossible = isPathUtil(
head.next, root.left)
|| isPathUtil(
head.next, root.right);
}
// Recursive calling for the next
// elements of the binary tree
return isPossible || isPath(head, root.left)
|| isPath(head, root.right);
}
// Driver Code
public static void main(String[] args)
{
treeNode root = new treeNode(1);
root.left = new treeNode(2);
root.right = new treeNode(3);
root.left.left = new treeNode(4);
root.left.right = new treeNode(5);
root.left.right.left = new treeNode(7);
root.right.right = new treeNode(6);
root.right.right.left = new treeNode(8);
root.right.right.right = new treeNode(9);
listNode head = new listNode(3);
head.next = new listNode(6);
head.next.next = new listNode(8);
// Function Call
System.out.print((isPath(head, root) ? "Yes" : "No"));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python program for the above approach # Node of the Linked list class listNode: # Constructor def __init__ (self, data): self.val = data; self.next = None; # Node of the Binary Search tree class treeNode: # Constructor def __init__ (self, data): self.val = data; self.left = None; self.right = None; # Recursive function to check if there # exist a path from the node curTree # having the LL from the node curList def isPathUtil(curList, curTree): # If the complete linked list # is traversed if (curList == None): return True; # If the tree node doesnot exist if (curTree == None): return False; if (curList.val == curTree.val): # Recursively calling for the # next element return ( isPathUtil(curList.next, curTree.left) or isPathUtil(curList.next, curTree.right) ); else: # If not found, return false return False; # Function to check if the linked list # exist as a downward path in Binary tree # using the DFS Traversal of the Tree def isPath(head, root): # If the current node of the # tree is None if (root == None): return False; # If the complete linked list # has been found if (head == None): return True; # Stores if there exist the # required path isPossible = False; if (root.val == head.val): # Recursively calling to # check the next node of # the linked list isPossible = isPathUtil(head.next, root.left) or isPathUtil(head.next, root.right); # Recursive calling for the next # elements of the binary tree return isPossible or isPath(head, root.left) or isPath(head, root.right); # Driver Code root = treeNode(1); root.left = treeNode(2); root.right = treeNode(3); root.left.left = treeNode(4); root.left.right = treeNode(5); root.left.right.left = treeNode(7); root.right.right = treeNode(6); root.right.right.left = treeNode(8); root.right.right.right = treeNode(9); head = listNode(3); head.next = listNode(6); head.next.next = listNode(8); # Function Call print( "Yes" if isPath(head, root) else "No"); # This code is contributed by saurabh_jaiswal.
C#
// C# program for the above approach
//include "bits/stdJava.h"
using System;
public class GFG{
// Node of the Linked list
class listNode {
public int val;
public listNode next;
// Constructor
public listNode(int data)
{
this.val = data;
next = null;
}
};
// Node of the Binary Search tree
class treeNode {
public int val;
public treeNode right;
public treeNode left;
// Constructor
public treeNode(int data)
{
this.val = data;
this.left = null;
this.right = null;
}
};
// Recursive function to check if there
// exist a path from the node curTree
// having the LL from the node curList
static bool isPathUtil(listNode curList,
treeNode curTree)
{
// If the complete linked list
// is traversed
if (curList == null)
return true;
// If the tree node doesnot exist
if (curTree == null)
return false;
if (curList.val == curTree.val) {
// Recursively calling for the
// next element
return isPathUtil(curList.next,
curTree.left)
|| isPathUtil(curList.next,
curTree.right);
}
else {
// If not found, return false
return false;
}
}
// Function to check if the linked list
// exist as a downward path in Binary tree
// using the DFS Traversal of the Tree
static bool isPath(listNode head, treeNode root)
{
// If the current node of the
// tree is Null
if (root == null)
return false;
// If the complete linked list
// has been found
if (head == null)
return true;
// Stores if there exist the
// required path
bool isPossible = false;
if (root.val == head.val) {
// Recursively calling to
// check the next node of
// the linked list
isPossible = isPathUtil(
head.next, root.left)
|| isPathUtil(
head.next, root.right);
}
// Recursive calling for the next
// elements of the binary tree
return isPossible || isPath(head, root.left)
|| isPath(head, root.right);
}
// Driver Code
public static void Main(String[] args)
{
treeNode root = new treeNode(1);
root.left = new treeNode(2);
root.right = new treeNode(3);
root.left.left = new treeNode(4);
root.left.right = new treeNode(5);
root.left.right.left = new treeNode(7);
root.right.right = new treeNode(6);
root.right.right.left = new treeNode(8);
root.right.right.right = new treeNode(9);
listNode head = new listNode(3);
head.next = new listNode(6);
head.next.next = new listNode(8);
// Function Call
Console.Write((isPath(head, root) ? "Yes" : "No"));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program for the above approach
// Node of the Linked list
class listNode
{
// Constructor
constructor(data) {
this.val = data;
this.next = null;
}
}
// Node of the Binary Search tree
class treeNode
{
// Constructor
constructor(data) {
this.val = data;
this.left = null;
this.right = null;
}
}
// Recursive function to check if there
// exist a path from the node curTree
// having the LL from the node curList
function isPathUtil(curList, curTree)
{
// If the complete linked list
// is traversed
if (curList == null) return true;
// If the tree node doesnot exist
if (curTree == null) return false;
if (curList.val == curTree.val)
{
// Recursively calling for the
// next element
return (
isPathUtil(curList.next, curTree.left) ||
isPathUtil(curList.next, curTree.right)
);
}
else
{
// If not found, return false
return false;
}
}
// Function to check if the linked list
// exist as a downward path in Binary tree
// using the DFS Traversal of the Tree
function isPath(head, root)
{
// If the current node of the
// tree is null
if (root == null) return false;
// If the complete linked list
// has been found
if (head == null) return true;
// Stores if there exist the
// required path
let isPossible = false;
if (root.val == head.val) {
// Recursively calling to
// check the next node of
// the linked list
isPossible =
isPathUtil(head.next, root.left) || isPathUtil(head.next, root.right);
}
// Recursive calling for the next
// elements of the binary tree
return isPossible || isPath(head, root.left) || isPath(head, root.right);
}
// Driver Code
let root = new treeNode(1);
root.left = new treeNode(2);
root.right = new treeNode(3);
root.left.left = new treeNode(4);
root.left.right = new treeNode(5);
root.left.right.left = new treeNode(7);
root.right.right = new treeNode(6);
root.right.right.left = new treeNode(8);
root.right.right.right = new treeNode(9);
let head = new listNode(3);
head.next = new listNode(6);
head.next.next = new listNode(8);
// Function Call
document.write(isPath(head, root) ? "Yes" : "No");
// This code is contributed by saurabh_jaiswal.
</script>
Producción:
Yes
Complejidad de Tiempo: O(N * M) donde N = Número de Nodes en el Árbol Binario y M = Número de Nodes en la lista Vinculada.
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por kartikey134 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA