сборка дерева из списка

Идея от permeakra очень даже разумна. Если у нас есть развёртка дерева после обхода in width, то мы можем собрать его без особых усилий, начиная с нижнего слоя. При сборке слоя n-1, мы используем поддеревья с уровня n, то есть каждый раз только конструируем деревья.

Главной проблемой является определение, где последний слой находится. Напоминаю, вот так вот выглядит запись дерева от leetcode:

Some(1), Some(2), Some(3), Some(4), None, None, Some(7), Some(8),

а вот так вот выглядит полная запись:

1 2 3 4 None None 7 8 None None None None None

Обратите внимание на количество None после 8. Если мы хотим строить дерево "снизу", то нам нужно восстановить все эти none, что совсем не просто. Хвостовые none могут относиться к разным слоям (дерево 1,2,3,4, None, None, None, 5) будет содержать "неявные none на нижнем уровне и уровне выше нижнего.

Так же, дерево не является сбалансированным, то есть мы не можем использовать binary heap формулу.

Моя текущая идея: идти по значениям и вычислять, сколько будет на следующем уровне. Каждый Some добавляет 2 к следующему уровню. None - не добавляет. Каждый уровень считается независимо. В конце мы можем обнаружить, что части значений не хватает. Мы дополняем список генератором None (видимо, бесконечным, для удобства), но останавливаемся в посчёте, когда для следующего уровня глубина 0. (таким образом, наш нижний слой всегда состоит только из None).

После того, как размеры слоёв (и полный размер дерева с учётом пропущенного хвоста) посчитаны, мы можем начать реконструировать нижний слой, который тривиален - это None... Может быть, это можно пропустить?.

Когда мы формируем слой, мы его сканируем в любом направлении (но в одном и том же для всех слоёв), и берём из списка поддеревьев по 2  для каждого формируемого элемента.

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

таким образом, мы превращаем список элементов в список размеров слоёв.
Дополняем входной список нужным количеством none.
Строим нижний слой (копируем нужное количество none) в список "предыдущего слоя".
Начинаем идти по размерам слоёв (снизу, от leaf)
Для каждого слоя берём n элементов из входного списка, в потомки к каждому элементу забираем по два элемента со списка предыдущего слоя. Собранные поддеревья кладём в тот же список (в начало).
В конце у нас один слой с размером 1, один элемент, мы кладём его в список (происходит автоматически)
Забираем поддерево из списка, это и есть искомое дерево.

Да, кажется, сработает. Ща попробую.


UPD: Я начал писать. При кажущейся простоте, получается очень много строк: Вот это всего лишь генерирует размеры слоёв.

let mut layer_sizes = Vec::new();

let mut layer_size = 1;

let mut elements = source.iter().chain(std::iter::repeat(&None));

while layer_size > 0 {

layer_sizes.push(layer_size);

layer_size = (&mut elements)

.take(layer_size)

.filter(|x| x.is_some())

.count()

* 2;

}

println!("{:?}", layer_sizes);

И потом ещё в полтора раза больше самой работы. Плюс там баг, а мне трудно понять где именно (заканчиваются subtree раньше, чем ожидалось), так что нет. Вариант в лоб - всего 22 строки.