Patrzę na książkę z wywiadem, a pytanie brzmi:

Masz dwa bardzo duże drzewa binarne:T1, z milionami węzłów iT2, z setkami węzłów. Utwórz algorytm, aby zdecydować, czyT2 jest poddrzewemT1.

Autorzy wspominają o tym jako o możliwym rozwiązaniu:

Zauważ, że problem tutaj określa toT1 ma miliony węzłów - oznacza to, że powinniśmy uważać, ile miejsca zajmujemy. Powiedzmy, na przykład,T1 ma 10 milionów węzłów - oznacza to, że same dane dotyczą40 mb. Moglibyśmy stworzyć ciąg reprezentujący przemieszczenie inorder i preorder. JeśliT2Przejście przedpremierowe jest podtekstemT1„Przejazd przedpremierowy” iT2Inorder Traversal jest podciągnikiemT1W tym samym czasieT2 jest substratemT1.

Nie jestem do końca pewien logiki, dlaczego tak jest:

T2-preorder-traversal-string jest substratemT1-preorder-traversal-stringT2-inorder-traversal-string jest substratemT1-inorder-traversal-string

ŻeT2 musi być podciągiem (chociaż zakładam, że autor oznacza poddrzewo) zT1. Czy mogę uzyskać wyjaśnienie tej logiki?

EDYTOWAĆ: UżytkownikBartosz Marcinkowski przynosi dobry punkt. Załóżmy, że oba drzewa nie mają duplikatów węzłów.