Ссылка на задачу — 889. Construct Binary Tree from Preorder and Postorder Traversal.
📌 Описание задачи
Нам даны прямой (preorder) и обратный (postorder) обходы бинарного дерева.
Необходимо восстановить дерево по этим обходам.
Основные свойства обходов:
- Preorder (прямой обход):
[корень → левый → правый]
- Postorder (обратный обход):
[левый → правый → корень]
💡 Идея
Для построения дерева используем рекурсивный подход, основанный на двух ключевых наблюдениях:
- 1️⃣ Каждый новый узел получает значение из
preorder
→ так мы всегда сначала создаем корень поддерева.
- 2️⃣ Поддерево считается полностью построенным, когда его значение встречается в
postorder
→ это сигнал к завершению рекурсии.
🔍 Детали подхода
- Используем итераторы
Peekable<Iterator> для эффективного прохода по preorder и postorder.
- Берем значение из
preorder и создаем новый узел.
- Рекурсивно создаем левое поддерево, если
postorder пока не указывает на текущий корень.
- Рекурсивно создаем правое поддерево, если
postorder всё ещё не дошел до корня.
- Как только postorder встречает значение корня, это означает, что всё поддерево полностью собрано, и мы возвращаемся из рекурсии.
⚡ Важно:
Используем итераторы вместо Vec::remove(0), чтобы не допустить квадратичного времени из-за смещения элементов.
⏳ Асимптотика/
-
Временная сложность:
O(N)
- Каждый узел обрабатывается ровно один раз, операции
peek() и next() работают за O(1) амортизированно.
-
Пространственная сложность:
O(N)
- Для стека рекурсии, глубина которой линейна в худшем случае.
📜 Исходный код
use std::rc::Rc;
use std::cell::RefCell;
use std::iter::Peekable;
use std::vec::IntoIter;
// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
struct TreeBuilder{
preorder: Peekable<IntoIter<i32>>,
postorder: Peekable<IntoIter<i32>>,
}
impl Solution {
pub fn construct_from_pre_post(preorder: Vec<i32>, postorder: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
let mut builder = TreeBuilder {
preorder: preorder.into_iter().peekable(),
postorder: postorder.into_iter().peekable(),
};
builder.build_subtree()
}
}
impl TreeBuilder {
/// Helper function to create an `Rc<RefCell<TreeNode>>` subtree
fn build_subtree(&mut self) -> Option<Rc<RefCell<TreeNode>>> {
match self.preorder.peek() {
Some(_) => Some(Rc::new(RefCell::new(self.construct_tree_node()))),
_ => None,
}
}
fn construct_tree_node(&mut self) -> TreeNode {
// Ensure `preorder` always has elements when calling this function
let Some(root_val) = self.preorder.next() else {
unreachable!("preorder should always have elements on construct_tree_node call")
};
let mut node = TreeNode { val: root_val, left: None, right: None };
// If postorder's next value isn't the root, construct subtrees
if self.postorder.peek() != Some(&root_val) {
node.left = self.build_subtree();
if self.postorder.peek() != Some(&root_val) {
node.right = self.build_subtree();
}
}
// Ensure postorder correctness
if self.postorder.next() != Some(root_val) {
panic!("Invalid input: postorder sequence does not match expected structure");
}
node
}
}
Tags: #rust #algorithms #tree #recursion