post-tree

[amarao]

Интернеты говорят, что во-первых Rc<RefCell> не идиоматично для Rust (деревья правильно держать как банальные вектора, содержащие в себе вектора векторов). Во-вторых, я, в целом, всё правильно сделал.

После некоторого кумекания получилось вот так вот, и я не вижу как его сделать существенно компактнее. Может быть, можно уйти от Enum и бального true/false хватит?

Да, получилось.

fn mktree(source: &[Option<i32>]) -> Tree {

if source.is_empty() || source[0].is_none() {

return None;

}

let tree: Tree = new_tree(source[0].unwrap());

let mut buff = VecDeque::new();

buff.push_back((tree.as_ref().cloned(), false));

for val in source[1..].into_iter() {

let subtree = val.and_then(|val| {

let subtree = new_tree(val);

buff.push_back((subtree.as_ref().cloned(), false));

subtree

});

let (node, is_last) = buff.pop_front().unwrap();

if is_last {

node.unwrap().borrow_mut().right = subtree;

} else {

node.as_ref().unwrap().borrow_mut().left = subtree;

buff.push_front((node.as_ref().cloned(), true));

}

}

tree

}

Что меня смущает? Изобилие as_ref().cloned(). Ща буду думать...

Comments

[eterevsky]

Rc плохо в дереве, потому что там реально будет каунтер обновляться, который там не нужен.

Что-то я не понял твой код. Выглядит как будто ты делаешь дерево высотой ровно 2. Можешь линкануть задачу, которую ты решаешь?

[amarao]

Тип для дерева придуман leetcode'ом. Интернеты его ругают. Дерево я делаю произвольной длины (если ты вчитаешься в алгоритм, там "потомки" созданных нод вставляются в конец очереди, то есть к ним потом тоже потомков дописывают).

Я решал не задачу с leetcode'а, а задачу конвертации примеров leetcode'а в дерево, для которого leetcode даёт задачу. В main там простейший пример несбалансированного дерева

https://github.com/amarao/leetcode-tree-build

Задача, к которой я решаю эту задачу простая (проверка дерева на симметричность), но у leetcode'а большинство задач на деревья в Rc сделаны, так что я решил себе тестовую остнастку сделать. Ну и заодно плотно познакомился с rc и refcell. (задача: https://leetcode.com/problems/symmetric-tree/)

[eterevsky]

А-а-а, всё, я теперь понял. Я не понимал в каком порядке элементы из списка должны вставляться в массив.

В том формате, в котором они написаны в задаче, тебе вообще не обязательно их конвертировать в дерево. Почитай как binary heap устроен. Дерево представляется массивом. У элемента i дети 2*i + 1 и 2*i + 2.

[amarao]

Ну, тут специфичная ситуация, когда входящие данные (в код) в конкретном формате (дерево - это Option Rc RefCell TreeNode), а тестовые примеры - в другом.

Вообще, я во всё это ввязался (до определённого момента я игнорировал задачи про деревья), чтобы хорошо разобраться во всех этих Rc/RefCell. Вроде бы, разобрался.

[amarao]

а, да, ещё. Формула 2*i не работает, потому что дерево-то может быть несбалансированным. 1, null, 2, null, 3, null, 4, null, 5, 6,7

[eterevsky]

Да, но если входные данные всё равно передаются в формате такого массива, то делать с ними ничего не надо. Просто массив будет Vec<Optional<...>>