Почему обход по порядку и по порядку полезен для создания алгоритма, чтобы решить, является ли T2 поддеревом T1
Я смотрю на книгу интервью и вопрос:
У вас есть два очень больших двоичных дерева:T1с миллионами узлов иT2с сотнями узлов. Создать алгоритм, чтобы решить, еслиT2 это поддеревоT1.
Авторы упоминают это как возможное решение:
Обратите внимание, что проблема здесь указывает на то, чтоT1 имеет миллионы узлов - это означает, что мы должны быть осторожны с тем, сколько места мы используем. Скажем, например,T1 имеет 10 миллионов узлов - это означает, что одни данные о40 mb. Мы могли бы создать строку, представляющую обходы inorder и preorder, ЕслиT2Обход предзаказа является подстрокойT1Обход предзаказа, иT2Обход по порядку является подстрокойT1Затем по порядку следованияT2 подстрокаT1.
Я не совсем уверен в логике того, почему это так:
T2-preorder-traversal-string подстрокаT1-preorder-traversal-stringT2-inorder-traversal-string подстрокаT1-inorder-traversal-stringЭтоT2 должна быть подстрокой (хотя я предполагаю, что автор означает поддерево)T1, Могу ли я получить объяснение этой логике?
РЕДАКТИРОВАТЬ: ПользовательBartoszMarcinkowski поднимает хороший вопрос. Предположим, что оба дерева не имеют повторяющихся узлов.