Недавно мои вопросы были помечены как дубликаты, какэтот даже если бы они не были. Итак, позвольте мне начать со следующего, а затем я объясню свой вопрос.

Почему этот вопрос не является дубликатом?

яне спрашиваю как создать бинарное дерево, когда заданы обход и предзаказ. Я прошу доказательство того, что обход inorder + preorder определяет уникальное двоичное дерево.

Теперь, чтобыоригинальный вопрос, Я пошел на собеседование, и интервьюер задал мне этот вопрос. Я застрял и не мог продолжить. : |

Вопрос: Даны обходы и порядок бинарного дерева. Докажи, что естьвозможно только одно двоичное дерево с данными данными. Другими словами, докажите, что два разных бинарных дерева не могут иметь одинаковые обходы и обходы. Предположим, что все элементы в дереве уникальны (спасибо @envy_intelligence за указание на это предположение).

Я пытался убедить интервьюера, используя примеры, но интервьюер спрашивал математическое / интуитивное доказательство. Может ли кто-нибудь помочь мне доказать это?