Вказівки
Уявімо, що нам потрібно передати бінарне дерево на супутник, який наближається до Альфи Центавра, а пропускна здатність у нас обмежена.
Оскільки в дереві немає повторюваних елементів, його однозначно задають обходи pre-order та in-order.
Напишімо програмне забезпечення для супутника, яке відновить дерево з цих обходів.
Обхід pre-order читає значення поточного вузла перед (звідси «pre») читанням лівого піддерева в порядку pre-order. Після цього в порядку pre-order читається праве піддерево.
Обхід in-order читає ліве піддерево в порядку in-order, потім поточний вузол і, нарешті, праве піддерево в порядку in-order. Тобто по порядку зліва направо.
Наприклад, обхід pre-order цього дерева такий: [a, i, x, f, r]. Обхід in-order цього дерева такий: [i, a, f, x, r].
a
/ \
i x
/ \
f r
Зауваження: перший елемент обходу pre-order - це завжди корінь.
Повідомлення винятків
Іноді буває потрібно підняти виняток. Коли ми це робимо, варто завжди додавати змістовне повідомлення про помилку, яке вказує на джерело помилки. Це робить код зрозумілішим і суттєво допомагає з налагодженням. Якщо відомо, що джерело помилки матиме певний тип, можна підняти один із вбудованих типів помилок, але повідомлення все одно має бути змістовним.
У цій вправі потрібно використати інструкцію raise, щоб «підняти» ValueError, якщо аргументи preorder та inorder не збігаються за довжиною, за елементами або якщо елементи не є унікальними. Тести пройдуть лише тоді, коли ми і виконаємо raise для exception, і додамо до нього повідомлення.
Щоб підняти ValueError з повідомленням, напишіть це повідомлення як аргумент до типу exception:
# if preorder and inorder are not the same length
raise ValueError("traversals must have the same length")
# if preorder and inorder do not share the same elements
raise ValueError("traversals must have the same elements")
# if element repeat (are not unique)
raise ValueError("traversals must contain unique items")
