У меня есть двоичное дерево с «длиной» (значением) каждого ребра.Я хочу собрать все возможные суммы этих ребер ≤ k.Давайте рассмотрим пример.
Правила просты.Я должен собрать все комбинации краевых сумм от пересечения корней.При k = 4 дерево из изображения будет иметь такие суммы, как [3,2,4,3,4,2,3].Как вы можете видеть, все, что мне нужно сделать, это использовать postorder и создать список со списком значений левого края, значения правого сына, суммы левого и правого края и передать его на родительский узел (игнорировать значения ≤ k. Отец будетвозьмите такие списки с левой стороны, с правой стороны, добавьте себя и вставьте их выше и т. д. Итак, теперь вопрос. Я знаю, что сложность времени обхода после заказа составляет O (n), но я не уверен, что теперь будет с этими списками.должен сделать что-то вроде
current_edge_list = left_list + right_list
current_edge_list.push(self_val)
for edge_from_left in left_list:
for edge_from_right in right_list:
current_edge_list.push(edge_from_left+edge_from_right)