preorder_vals — прямой обход: сначала вершина, затем её левое поддерево, затем правое;
- postorder_vals — обратный обход: левое поддерево, затем правое, и только потом сама вершина.
Восстановите дерево и верните его корень.
Эти два обхода не различают, левый у вершины единственный ребёнок или правый. Поэтому договоримся: если у вершины ровно один ребёнок, делайте его **левым**. При таком правиле ответ единственный. Гарантируется, что оба списка получены из одного и того же дерева.preorder_vals=[1, 2, 4, 3, 5], postorder_vals=[4, 2, 5, 3, 1] → [1, 2, 3, 4, None, 5]
Корень 1. Следующий в прямом обходе — 2, это корень левого поддерева; в обратном обходе 2 стоит после 4, значит левое поддерево — {2, 4}, а правое — {3, 5}. У 2 единственный ребёнок 4, у 3 — 5; по правилу оба становятся левыми детьми.
preorder_vals=[1, 2, 3], postorder_vals=[3, 2, 1] → [1, 2, None, 3]
По обходам не понять, с какой стороны висят дети, поэтому каждый единственный ребёнок — левый: цепочка 1 → 2 → 3 влево.
preorder_vals=[2, 1, 3], postorder_vals=[1, 3, 2] → [2, 1, 3]
preorder_vals=[1, 2, 4, 3, 5], postorder_vals=[4, 2, 5, 3, 1]
[1, 2, 3, 4, None, 5]
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 28 тестов на сервере, включая скрытые.