Encuentra el subárbol raíz que contiene un conjunto predefinido de valores.

Dado un árbol de nodos, encuentra un subárbol arraigado que contenga un conjunto de valores predefinidos. Los nodos en el árbol son únicos pero sus valores asociados pueden repetirse.

Idealmente, se devuelve el subárbol más superficial. El subárbol también se puede devolver simplemente como un arreglo de nodos (o sus ID únicos).

Aquí hay varios casos de prueba atómicos con el subárbol resultante ideal:

1 [A, A, B, C]


A1 Respuesta: A1
/ | \ / \
B1 D1 C1 B1 C1
/ \ \ /
A2 B2 B3 A2


2 [A, B, B, A]


A1 Respuesta(s): A1 A1 A1 se prefiere la primera solución
/ \ / \ / \ ya que es más superficial
B1 B2 B1 B2 B1 B2
/ \ \ / / \ \
A2 B3 B4 A2 A2 B3 B4
\ \
A3 A3


3 [A, A, B, C]


A1 Respuesta: No es posible porque solo se puede emparejar un B
/ \
B1 B2
/ \
A2 C1


4 [B, B]


A1 Respuesta: No es posible ya que la raíz 'A' no está en el conjunto
/ \
B1 B2


Mi enfoque se dividió en dos pasos:
1. Escaneo en anchura hasta que se encuentren todos los nodos en el conjunto, devolviendo un árbol que definitivamente contiene el subárbol deseado.
2. Utilizar la retrotrazabilidad para buscar en el subárbol resultante (esencialmente todas las permutaciones del subárbol) para encontrar los nodos exactos que satisfacen el conjunto.

Sin embargo, esta solución no es muy eficiente. Parece que debería poder encontrar el subárbol deseado simplemente usando una búsqueda en anchura modificada. También he sido incapaz de hacer que esto funcione en la práctica.