Найти все пути дерева

Как найти количество путей в дереве с определенным весом?

Начинаю идти с конца массива (дерева) и добавляю вес к сумме. Начинаю цикл, пока не дойду до корня и сумма не превосходит X , перехожу к родителю и повторяю предыдущее действие. После окончания цикла смотрю сумма в точности равна X или нет, если да, то увеличиваю счётчик на 1, иначе не делаю ничего. Перед переходом у следующей вершине обнуляю сумму

class Vertex < constructor(weight, parent) < this.weight = weight; this.parent = parent; >> function getNumberOfUpgoingPaths(tree, x) < let count = 0; let sum = 0; for (let i = tree.length - 1; i >= 0; --i) < const vertex = tree[i]; let parentIndex = vertex.parent; sum += vertex.weight; while(parentIndex !== -1 && sum < x) < const parentVertex = tree[parentIndex]; sum += parentVertex.weight; parentIndex = parentVertex.parent; >if (sum === x) ++count; sum = 0; > return count; > // Обработка входных данных const inputs = document.querySelector('#inputs'); const startAlgorithm = () => < console.clear(); const tree = []; const [[countOfvertexes, x], . vertexes] = inputs.value.split('\n').map(x =>x.split(' ').map(Number)); vertexes.forEach(vertex => tree.push(new Vertex(vertex[1], vertex[0]))) console.log(getNumberOfUpgoingPaths(tree, x)); > startAlgorithm(); inputs.addEventListener('input', startAlgorithm);

6 3 -1 1 0 1 0 1 1 1 2 2 3 1

Если хотите менять данные, то формат ввода таков:

• В первой строке первые 2 числа — это количество вершин и X (число вершин при обработке игнорируется, но писать его нужно, чтобы не ломать формат ввода данных)
• Начиная со второй строки перечисляются вершины, где левое число — это номер родителя, а правое число — это вес вершины

На каком-то из тестов (в яндексе не показывается на каком тесте) он ломается — возвращает неверный результат. На тестах, которые я сам придумывал, алгоритм работает верно. Помогите пожалуйста найти ошибку в рассуждениях или хотябы тест кейс, на котором всё ломается, дальше уже думаю смогу сам исправить ошибку

Было бы полезно добавить, какие именно тесты вы написали. Вероятно, что-то не учли (например пустое дерево, или из 1 вершины, итп). Т.к. одно дело это подсказать вам алгоритм решения, Второе — подсказать неучтенные тесты, Третье — исправить ошибки в вашем алгоритме и коде.

«Яндекс Контест. Задача G. Пути в дереве.» — для названия вопроса это бесполезные сведения. Завтра эта задача будет на ЛитКоде, послезавтра в задачнике Гурина. Номер задачи — аналогично. Название задачи также не описательно.

@Kromster Не надо из заголовка убирать название задачи. Я их специально написал, чтобы следующий, кто захочет нагуглить проблему, мог найти по названию задачи. Для тест кейсов я добавил интерактивный код, где можно написать любой тест кейс. Я просто тестировал очень много тест кейсов включая то что вы указали (дерево пустым не может быть) и не вижу смысла писать их сюда — получится слишком много

«для названия вопроса это бесполезные сведения» — я много раз находил именно так решение конкретной задачи. Потому не считаю это бесползеным

Такой заголовок гораздо лучше, чем «как решить задачу». Однако в заголовке, в общем-то, достаточно последнего предложения, т.к. информация об источнике и в теле вопроса будет искаться.

2 ответа 2

Вы упустили, что вес вершины может быть отрицательным

w_i - вес вершины: −10^4 ≤ w_i ≤ 10^4 

А по эффективности — в последней теме вы должны были кой-чему научиться.

пример на Python для подъёма из одного листа

from collections import Counter import random #a = [1, 2 , -2, 2] #a = [random.randint(-3,5) for _ in range(6)] a = [-1, 0, 3, 3, -2, 2] print(a) X = 3 res = 0 #следующие две строки должны выполняться при старте из каждого листа cnt = Counter() summ = 0 print(summ, end = ' ') for v in a: summ += v print(summ, end = ' ') res += cnt[summ - X] cnt[summ] += 1 #здесь пометить узел, чтобы больше с него не стартовать print() print(res) [-1, 0, 3, 3, -2, 2] #последовательность значений 0 -1 -1 2 5 3 5 #накопленные суммы 5 #результат - 5 путей 

Нет, я учёл, что они отрицательные могут быть, по крайней мере по моим тестам с отрицательными числами всё работало корректно. Если веса отрицательные, то сумма будет уменьшаться, значит условие sum < x тем более будет выполняться, а значит он не остановится из-за него

За линейное время для каждого пути от листа. Что в целом получится, я затрудняюсь сказать. И помечать пройденные внутренние узлы, чтобы с них не стартовать

короче решенная задача на с++, основанная на вот этом тексте: https://www.techiedelight.com/ru/count-paths-with-given-sum-binary-tree/ Но по-моему там ошибка, потому что там сначала прибавляется map[sum_so_far] += 1; и только потом считается long count = map[sum_so_far — k]; у меня этот алгоритм работал некорректно. Этот прошел тест

#include #include #include #include #include #include using namespace std; struct Vertex < long weight; long parent; Vertex(long w1, long p1) < weight = w1; parent = p1; >>; vector> createReverseTree(const vector& treeOrig) < long n = treeOrig.size(); vector> reverseTree(n); for (int i = 0; i < n; i++) < int parent = treeOrig[i].parent; if (parent < 0) < continue; >reverseTree[parent].push_back(i); > return reverseTree; > // Функция для рекурсивного обхода дерева от корня до листьев long traverseTree( const vector>& reverseTree, vector& treeOrig, long node, long k, long sum_so_far, std::unordered_map& map ) < Vertex& curVertex = treeOrig[node]; sum_so_far += curVertex.weight; // получаем количество путей с суммой `k`, которые заканчиваются текущим узлом long count = map[sum_so_far - k]; map[sum_so_far] += 1; for (long child : reverseTree[node]) < count += traverseTree(reverseTree, treeOrig, child, k, sum_so_far, map); >map[sum_so_far] -= 1; return count; > int root = 0; vector readTree(long n) < vectortree; for (long i = 0; i < n; i++) < long parent, weight; cin >> parent >> weight; Vertex v(weight, parent); if (parent < 0) < root = i; >tree.push_back(v); > return tree; > long getNumberOfUpgoingPaths(vector& treeOrig, long x) < long resVal = 0; auto tree = createReverseTree(treeOrig); unordered_mapmap; map[0] = 1; resVal = traverseTree(tree, treeOrig, root, x, 0, map); return resVal; > int main() < int n; cin >> n; long x; cin >> x; vector tree = readTree(n); cout

Источник

Вывести все пути от корня до листовых узлов бинарного дерева

Для заданного бинарного дерева напишите эффективный алгоритм для вывода всех путей от корневого узла до каждого конечного узла в нем.

Например, рассмотрим следующее бинарное дерево:

The binary tree has four root-to-leaf paths:

1 —> 2 —> 4
1 —> 2 —> 5
1 —> 3 —> 6 —> 8
1 —> 3 —> 7 —> 9

Идея состоит в том, чтобы обойти дерево в предзаказ моды и сохранить каждый встреченный узел на текущем пути от корня к листу в векторе. Если мы встретим листовой узел, выведите все узлы, присутствующие в векторе. Ниже приведена реализация этой идеи на C++, Java и Python:

C++

результат:

1 2 4
1 2 5
1 3 6 8
1 3 7 9

Java

результат:

[1, 2, 4]
[1, 2, 5]
[1, 3, 6, 8]
[1, 3, 7, 9]

Python

результат:

[1, 2, 4]
[1, 2, 5]
[1, 3, 6, 8]
[1, 3, 7, 9]

Временная сложность приведенного выше решения равна O(n) , куда n это общее количество узлов в бинарном дереве. Программа требует O(h) дополнительное место для стека вызовов, где h это высота дерева.

Проблема кажется немного сложной для решения без рекурсии. Существует один обходной путь, когда мы сохраняем путь от корня к листу в строке, когда мы итеративно проходим по дереву, и печатаем путь всякий раз, когда встречаем какой-либо конечный узел. Это показано ниже на C++, Java и Python:

Источник

Поиск всех путей максимальной длины в дереве

Есть бинарное дерево, пусть оно будет сбаллансированное. Необходимо найти глубину дерева (максимальное расстояние от корня до листа) и вернуть все пути в дереве (их почти гарантированно несколько) с этой глубиной. Структура ноды дерева

int * arr = new int[n]; for (size_t i = 0; i < n; i++) < arr[i] = i; >TreeNodeMod * head = CreateBalancedTree(arr, 0, n-1); 

TreeNodeMod * CreateBalancedTree(int arr[], int start, int end) < if (arr == nullptr) < return nullptr; >if (end < start) < return nullptr; >int mid = (start + end) / 2; TreeNodeMod *n = MakeNode(arr[mid]); n->leftChild = CreateBalancedTree(arr, start, mid - 1); n->rightChild = CreateBalancedTree(arr, mid + 1, end); return n; > TreeNodeMod * MakeNode(int x) < TreeNodeMod * n = new TreeNodeMod; n->data = x; n->leftChild = nullptr; n->rightChild = nullptr; return n; > 

void PrintTreeByLevel(TreeNodeMod * n) < int h = TreeHeight(n); auto prnt = [](auto&& self, TreeNodeMod * n, int lvl)< if (n == nullptr) < return; >if (lvl == 1) < std::cout data else < if (lvl >1) < self(self, n->leftChild, lvl-1); self(self, n->rightChild, lvl-1); > > >; for (int i = 1; i < h+1; i++) < prnt(prnt, n, i); std::cout > 

Возможно, для этого можно как-то модифицировать фукцию подсчета глубины дерева, но я не могу сообразить, как

size_t TreeHeight(TreeNodeMod * node) < if (node == nullptr) < return 0; >else < int lheight = TreeHeight(node->leftChild); int rheight = TreeHeight(node->rightChild); if (lheight > rheight) return(lheight + 1); else return(rheight + 1); > > 

Источник

Нахождение всех возможных путей из одной точки в другую в дереве — Python

Я пытаюсь изменить его, чтобы найти все возможные пути. Застрял на следующем моменте: как вернуть строку с уже найденным путем для следующей итерации цикла поиска из уже пройденной вершины — подставив в эту строку путь только до текущей вершины. Так же вопрос: как положить объявление списка всех путей внутрь функции, чтобы он потом не обнулялся при итерировании.

newpaths = [] # !ОБЪЯВЛЕНИЕ СПИСКА def search_all_paths(graph, start, end, path=[]): path += start if start == end: return path if start not in graph: return None for node in graph[start]: if node not in path: newpath = search_all_paths(graph, node, end, path) if newpath: print(newpath, newpaths, path) if newpath != newpaths: newpaths.append(newpath) newpath = [] path = [] # **!ВОТ ЭТОТ ПУТЬ. ** print('. ', newpath, newpaths, path) return newpaths 

2 ответа 2

В дереве путь между вершинами всегда единственный

Если задача всё-таки стоит для графа общего вида (судя по тому, что в C входят две дуги):

Для нахождения всех простых путей в заданную вершину нужно помечать пройденные вершины, чтобы не использовать их на дальнейших уровнях рекурсии, но эти пометки не должны быть глобальными.

Пример рекурсивной реализации на Delphi отсюда для небольшого числа вершин (до 32), для хранения текущих пометок используются биты целого числа.

Двумерный массив Adj работает как словарь со списками, shl — битовый сдвиг влево

Забит граф в виде шестиугольника с большим циклом 013652, и вершина 4 соединена с 0,3,5

var Adj: array of array of Byte; Src, Dest: Integer; procedure FindRoute(V: Integer; Used: Integer; Route: string); var i, W: Integer; begin if V = Dest then Memo1.Lines.Add(Route) else for i := 0 to High(Adj[V]) do begin W := Adj[V, i]; if (Used and (1 shl W)) = 0 then FindRoute(W, Used or (1 shl W), Route + IntToStr(W) + ' '); end; end; begin SetLength(Adj, 7); SetLength(Adj[0], 3); SetLength(Adj[1], 2); SetLength(Adj[2], 2); SetLength(Adj[3], 3); SetLength(Adj[4], 3); SetLength(Adj[5], 3); SetLength(Adj[6], 2); Adj[0, 0] := 1; Adj[1, 0] := 0; Adj[0, 1] := 2; Adj[2, 0] := 0; Adj[0, 2] := 4; Adj[4, 0] := 0; Adj[1, 1] := 3; Adj[3, 0] := 1; Adj[2, 1] := 5; Adj[5, 0] := 2; Adj[3, 1] := 4; Adj[4, 1] := 3; Adj[3, 2] := 6; Adj[6, 0] := 3; Adj[4, 2] := 5; Adj[5, 1] := 4; Adj[5, 2] := 6; Adj[6, 1] := 5; Src := 0; Dest := 3; FindRoute(Src, 1 shl Src, IntToStr(Src) + ' '); end; выдача 0 1 3 0 2 5 4 3 0 2 5 6 3 0 4 3 0 4 5 6 3 

# -*- coding: utf-8 -*- # Вывод всех путей из источника в пункт назначения. # Этот код предоставлен Neelam Yadav # Адаптирован Александром Драгункиным from collections import defaultdict # Класс направленного графа, использует представление списка смежности class Graph: def __init__(self, vertices): # Нет. вершин self.V = vertices # словарь по умолчанию для хранения графа self.graph = defaultdict(list) # функция добавления ребра в граф def addEdge(self, u, v): self.graph[u].append(v) '''Рекурсивная функция для печати всех путей от 'u' до 'd'. visit [] отслеживает вершины в текущем пути. path [] хранит актуальные вершины, а path_index является текущим индексом в path[]''' def printAllPathsUtil(self, u, d, visited, path): # Пометить текущий узел как посещенный и сохранить в path visited[list(self.graph.keys()).index(u)] = True path.append(u) # Если текущая вершина совпадает с точкой назначения, то # print(current path[]) if u == d: print(path) else: # Если текущая вершина не является пунктом назначения # Повторить для всех вершин, смежных с этой вершиной for i in self.graph[u]: if visited[list(self.graph.keys()).index(i)] == False: self.printAllPathsUtil(i, d, visited, path) # Удалить текущую вершину из path[] и пометить ее как непосещенную path.pop() visited[list(self.graph.keys()).index(u)] = False # Печатает все пути от 's' до 'd' def printAllPaths(self, s, d): # Отметить все вершины как не посещенные visited = [False] * (self.V) # Создать массив для хранения путей path = [] # Рекурсивный вызов вспомогательной функции печати всех путей self.printAllPathsUtil(s, d, visited, path) # Создаём граф graph = g = Graph(len(graph.keys())) for i, v in graph.items(): for e in v: g.addEdge(i, e) s = 'A' d = 'C' print ("Ниже приведены все различные пути от <> до <> :".format(s, d)) g.printAllPaths(s, d) 

Ниже приведены все различные пути от A до C : ['A', 'B', 'C'] ['A', 'B', 'D', 'C'] ['A', 'C'] 

Источник