Построение двоичного дерева из обходов в прямом и предварительном порядке ⇐ C++

[Гость]

У меня есть следующие последовательности:

Порядок: {4, 2, 5, 1, 6, 3} Предзаказ: {1, 2, 4, 5, 3, 6

Мне хотелось бы понять, как построить двоичное дерево из этих последовательностей и почему это возможно с помощью этой комбинации прямого и предварительного порядка, но не с некоторыми другими комбинациями. Кроме того, мне интересно узнать, как реализовать алгоритм для достижения этой цели на C++.

Вот мои конкретные вопросы:

Как построить двоичное дерево из заданных последовательностей прямого и предварительного порядка, таких как {4, 2, 5, 1, 6, 3} и {1, 2, 4, 5, 3, 6}? Почему можно построить дерево с помощью комбинаций Inorder + Preorder или Inorder + Postorder, но нельзя с помощью Preorder + Postorder? Может ли кто-нибудь предоставить подробный алгоритм и реализацию кода на C++ для построения двоичного дерева с использованием обходов Inorder и Preorder? Я ценю любые идеи и объяснения по этому поводу. Спасибо!
if (traversal_type == "pre") { root->left = buildTree(inorder, traversal, in_start, root_index - 1, t_start + 1, t_start + left_len, orderIndex, traversal_type); root->right = buildTree(inorder, traversal, root_index + 1, in_end, t_start + left_len + 1, t_end, orderIndex, traversal_type); } иначе, если (traversal_type == "сообщение") { root->right = buildTree(inorder, traversal, root_index + 1, in_end, t_start, t_end - 1, orderIndex, traversal_type); root->left = buildTree(inorder, traversal, in_start, root_index - 1, t_start, t_start + left_len - 1, orderIndex, traversal_type); }