Как создать двоичное дерево с заданными обходами?

Question

Итак, скажем, что нам даны два списка: значения обхода по предварительному порядку двоичного дерева и значения обхода по порядку, приведенные в списке. Теперь мне нужно создать дерево (в форме списка, например [1, [2, [2, None, None], None], [1, None, None]]). Я могу отличить корневое значение и количество элементов в каждой стороне дерева от значений обхода, но я немного сбит с толку относительно того, как создать само дерево. Является ли рекурсия хорошей идеей для этого вопроса, поскольку мы создаем поддеревья в основном дереве?

Это не может быть сделано с классами, либо. Это должна быть функция. Классы сделали бы это намного проще, но я не должен их использовать.

Answer 1

Это может быть полезно.

Резюме:
С помощью обхода по предварительному заказу [x1,…, xn] и обхода по порядку [z1,…, zn] вы можете перестроить дерево следующим образом:

Корень является главой обхода предварительного заказа x_1. Пусть k будет индексом таким, что z_k=x1. Тогда [z_1,…,z_k−1] - это обход по порядку левого потомка, а [z_k+1,…,z_n] - это порядок обхода правого потомка. Исходя из количества элементов, [x_2,…,x_k] является обходом предварительного порядка левого потомка, а [x_k+1,…,x_n] - правым потомком. Повторяйте, чтобы построить левое и правое поддеревья.