🚀 Рекурсивное восстановление бинарного дерева по прямому и обратному проходам.

leetcoder, 24-02-2025 ,

468

Ссылка на задачу — 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