если у вас есть обход по порядку и обход по порядку для общего двоичного дерева, они даже не определяют дерево однозначно, если вы можете иметь дублированные значения, например, последовательность [1,1,1] для пост-заказа и для-заказа может быть одним из следующих деревьев:
1 1
1 1 1
1
А путь с минимальной суммой имеет сумму 2 слева и сумму 3 справа.
Итак, предположим, что все значения различны.
Предположим, у вас есть список прохождения заказа [x1, x2, ..., xn] и список прохождения заказа [y1, ..., yk, ..., yn], так что xn == yk , Поскольку xn - корень дерева, теперь вы знаете, что [y1, ..., yk-1] - это левое поддерево, а [yk + 1, ..., yn] - правое поддерево. Тогда левое поддерево также представляется как [x1, ..., xk-1], поскольку размер левого поддерева, очевидно, является постоянным, поэтому вы можете разделить список обхода после заказа также между xk-1 и xk.
В качестве примера приведем несбалансированное двоичное дерево без какого-либо определенного порядка:
5
3 6
9 2 1
4
Обход в порядке [9,3,2,5,6,4,1] и пост-заказ [9,2,3,4,1,6,5].
Дерево будет рекурсивно сконструировано так: возьмите последний элемент прохождения после заказа (5); разделить по порядку на [9,3,2] и [6,4,1] (разделив в месте расположения элемента 5); таким образом, список прохождения после заказа разделяется на [9,2,3] и [4,1,6] только на основе известных теперь размеров поддеревьев. Затем рекурсия продолжается; давайте посмотрим на дерево [6,4,1], потому что оно не сбалансировано:
корень 6; в порядке [6,4,1] левое поддерево пусто, а правое - [4,1], поэтому из списка после заказа [4,1,6] вы берете [] в качестве левого поддерево и [4,1] как правое поддерево; оттуда вы получаете корневой узел 1 и обнаруживаете, что [4] является левым поддеревом; из которой вы получаете форму
6
1
4
по желанию.
Теперь, поскольку ваше дерево не упорядочено, не сбалансировано и т. Д., Вы можете просто попытаться написать рекурсивный код для обработки вашего запроса. Вот это в C ++:
const int size = 7; /* Size of the tree */
/* Given arrays */
int post_order[size] = { 3 , 1 , 2 , 5 , 6 , 7 , 4 };
int in_order[size] = { 3 , 2 , 1 , 4 , 5 , 7 , 6 };
/* Variables updated during recursion */
int min_sum = 99999999; /* not initialized */
int best_leaf = -1; /* not initialized */
/* Recursive descent */
/* prb = post-order range begin, irb = in-order range begin, etc. */
void min_sum_leaf(int acc, int prb, int irb, int len) {
if (len == 0) return; /* empty subtree */
if (len == 1) { /* leaf */
int sum = acc + in_order[irb];
if (sum<min_sum) { min_sum = sum; best_leaf = in_order[irb]; }
return;
}
/* non-leaf */
int subtree_root = post_order[prb + len - 1];
/* find the size of the left subtree */
int i;
for (i=0;i<len;i++) {
if (in_order[irb + i] == subtree_root) break;
}
/* Now i is the length of the left subtree, len - i - 1 of the right */
min_sum_leaf(acc + subtree_root, prb, irb, i);
min_sum_leaf(acc + subtree_root, prb + i, irb + i + 1, len - i - 1);
}
/* Driver */
int find_min_sum_leaf() {
min_sum = 99999999; best_leaf = -1;
min_sum_leaf(0, 0, 0, size);
return best_leaf;
}
Примечание: я не скомпилировал и не запустил алгоритм, но логика должна быть там!