tree traversal

[amarao]

Все эти возни на leetcode привели к тому, что я нашёл минималистичную конструкцию для обхода их странного Rc RefCell дерева.

pub fn postorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {

fn dive(t: &Option<Rc<RefCell<TreeNode>>>, acc: &mut Vec<i32>){

if let Some(rc) = t{

let node = rc.borrow();

dive(&node.left, acc);

dive(&node.right, acc);

acc.push(node.val);

}

}

let mut acc = Vec::new();

dive(&root, &mut acc);

acc

}

Ключевое открытие тут: с любым Rc надо работать только через ref/mut ref. Как только появляется владение Rc, начинаются массовые проблемы, потому что rc.as_ref() создаёт короткоживущий референс и начинаются всякие выкрутасы. А c ref всё очень хорошо. Во-первых &option<T> автоматом конвертируется в & T после `if let Some...`. После того, как у нас появляется &T, простой .borrow() даёт нам правильную сущность с lifetime блока Some. Дальше мы можем обращаться к содержимому по точке, потому что там Deref реализован (насколько я понимаю, это именно Deref).

Вторая штука, которую я подглядел у соседей по решению: вложенные функции очень удобны, потому что находятся внутри Solution и их легко рекурсивно вызывать без Solution:: и т.д. Вложенные функции в Rust довольно банальны и всего лишь "записаны локально". В отличие от питона у них нет никаких признаков захвата замыкания (в питоне вложенные функции - метод создания замыканий), т.е. это исключительно кнопкодавное удобство.

Comments

[juan_gandhi]

Вот этот код выглядит вполне замечательно.

[vak]

Красиво, и эффективно вполне.