Построить полное двоичное дерево из списка обхода предварительного порядка Python

Question

Как построить двоичное дерево (не двоичное дерево поиска) из списка предзаказ в Python, используя только встроенный список? Каждый узел в списке предзаказ также имеет «флаг», который показывает, является ли он листом или внутренним узлом. И каждый узел имеет 2-х детей (Нет 0 или 1 ребенка)

Я сделал класс для представления узла

class Node: 
    def __init__(self, initType): 
     self.type = initType 
     self.leftChild = None 
     self.rightChild = None 

Я думаю, что я должен использовать stack здесь, но я не хочу import в stack библиотека.

Решения, которые я нашел в Интернете, предназначены только для BST, или вход состоит из списка порядка и списка предварительных заказов, а не только списка предварительных заказов.

Answer 1

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

Например, если список предварительно заказ был дает в [1, 2, 3]

тогда исходный бинарное дерево может быть:

  1 
    /
    2 
/
    3 

или это может быть:

1 
    \ 
    2 
    \ 
    3 

** обратите внимание, как они являются разными деревьями, но будут иметь одинаковые списки обхода порядка!

Если бы этот вопрос задавали в интервью, это означало, что вы заметили тот факт, что уникальное бинарное дерево не может быть реализовано, и вы уточните вопрос: «Является ли бинарное дерево двоичным деревом поиска? "

В опросах очень часто не упоминаются факты из вопроса, на которые вы задаете вопросы.