По заданному бинарному дереву поиска и числу найдите путь, данные узла которого были добавлены к данному номеру.

Question

Учитывая двоичное дерево поиска и число, найдите, существует ли путь от корня к листу так, чтобы все числа на пути складывались, чтобы быть данным числом.

Я знаю, как сделать это рекурсивно. Но я предпочитаю итеративное решение.

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

Что если в дереве нет бинарного поиска?

Спасибо

Answer 1

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

Основная идея состоит в том, чтобы отслеживать возможные длины от каждого листа до данного узла в таблице f[node]. Если мы реализуем его в двумерном логическом массиве, это будет что-то вроде f[node][len], которое указывает, существует ли путь от листа до node с длиной, равной len. Мы также можем использовать vector<int> для хранения значения в каждом f[node] вместо использования логического массива. Независимо от того, какое представление вы используете, способ вычисления между различными f будет простым, в виде

f[node] is the union of f[node->left] + len_left[node] and f[node->right] + len_right[node].

Это случай двоичного дерева, но действительно легко распространить его на случаи не двоичного дерева.

Если что-то неясно, пожалуйста, не стесняйтесь комментировать.

Answer 2

Для BST:

Node current,final = (initialize)
List nodesInPath;
nodesInPath.add(current);
while(current != final) {
    List childrenNodes = current.children;
    if(noChildren) noSolution;
    if(current < final) {
        //choose right child if there is one, otherwise no solution
        current = children[right];
    } else if(current > final){
        //choose left child if there is one, otherwise no solution
        current = children[left];         
    } 
    nodesInPath.add(current);
}
check sum in the nodesInPath

Однако для не BST вы должны применить решение с использованием динамического программирования, как дерехх , если вы не хотите вычислять одни и те же пути снова и сноваснова.Я думаю, вы можете хранить общую длину между определенным обрабатываемым узлом и корневым узлом.Вы рассчитываете расстояния, когда расширяете их.Затем вы должны применить Breadth-first search, чтобы не пересекать те же пути снова и использовать ранее вычисленные общие расстояния.Алгоритм, на мой взгляд, немного сложен, извините, но не хватает времени, чтобы его написать.

Answer 3

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

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