Определите, является ли двоичное дерево поддеревом другого двоичного дерева, используя строки порядка и порядка

Я хочу узнать, является ли двоичное дерево T2 поддеревом двоичного дерева T1. Я прочитал, что можно было построить строковые представления для T2 и T1, используя предварительные и обходные обходы, и если строки T2 являются подстроками строк T1, T2 является поддеревом T1.

Я немного смущен этим методом и не уверен в его правильности.

Из wiki: "Поддерево дерева T является деревом, состоящим из node в T и всех его потомков в T."

В следующем примере:

Если мы построим строки для T2 и T1:

preorder T2: "1,2,3"
preorder T1: "1,2,3,4"
inorder T2: "2,1,3"
inorder T1: "2,1,3,4"

Строки T2 являются подстроками T1, поэтому, используя описанный выше метод согласования подстроки, мы должны заключить, что T2 является поддеревом T1.

Однако T2 по определению не должен быть поддеревом T1, поскольку он не имеет всех потомков корня T1 node.

Существует связанное обсуждение здесь, которое, похоже, завершает метод правильным.

Я что-то пропустил?

Ответ 1

Очень интересный вопрос. Кажется, ты прав. Я предполагаю, что проблема, о которой вы говорите, возникает из-за различных определений поддерева в математике (теория графов) и информатике. В теории графов T2 является собственным поддеревом T1.

Ответ 2

Предполагая, что вы получили это из книги "Раскрутка интервью по кодированию", автор также упоминает, что для различения узлов с одинаковыми значениями следует также печатать нулевые значения.

Это также решит вашу проблему с определением поддерева (что правильно, как описано в книге)

preorder T2: "1, 2, null, null, 3, null, null" preorder T1: "1, 2, null, null, 3, null, 4, null, null" inorder T2: "null, 2, null, 1, null, 3, null" inorder T1: "null, 2, null, 1, null, 3, null, 4, null"

Как вы можете видеть, T2 не является поддеревом T1

Ответ 3

Определение поддерева дерева должно быть таким же, как определение подстроки строки. Подумайте об этом так: 1. Подстрока начинается-с, содержит и заканчивается-с. 2. Дерево также должно иметь одно и то же определение, но обобщенное в соответствии с структурой данных дерева. 3. Обобщение от 1-мерного для строки до 2-мерного для дерева.

Ответ 4

Я читаю ту же книгу и сомневаюсь в ее решении. Я придумал еще один встречный пример, который не попадает в потенциальную интерпретацию, которую упоминает пользовательский ледпак (поддерева, не обязательно нуждающегося в всех потомках).

Рассмотрим следующие деревья

T2:
  B
 / \
A   C

T1:
    C
   / \
  B   C
 /
A

preorder T2: 'BAC'

Опять же, строки T2 являются подстроками их T1-аналогов, и все же T2 никоим образом не является поддеревом T1. Возможно, автор исключил дубликаты и конкретно упомянул о своем определении поддерева, это может быть правильно, но, оставляя эту информацию, у нас нет выбора, кроме как считать ее неправильным решением.

Ответ 5

Na... Этот подход неверен. Поскольку разные деревья могут иметь одинаковый обход. Например, здесь, в данном примере, дерево

         26
        /   \
      10     3
    /    \     \
  4      6      3
   \
    30

и поддеревья-кандидаты

имеют одинаковые обходные пути как 4,30,10,6 но второй не является поддеревом