Verifique si todos los elementos de la lista vinculada dada corresponden a una ruta descendente desde cualquier Node en el árbol binario dado

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

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

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

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)