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

Question

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

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

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

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

Спасибо

Answer 1

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

Основная идея состоит в том, чтобы отслеживать возможные длины от каждого листа до данного узла в таблице f[node], Если мы реализуем его в 2-мерном логическом массиве, это что-то вроде 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

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

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

Answer 3

Для 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 вы должны применить решение с использованием динамического программирования, как предлагает derekhh, если вы не хотите вычислять одни и те же пути снова и снова. Я думаю, вы можете хранить общую длину между определенным обрабатываемым узлом и корневым узлом. Вы рассчитываете расстояния, когда расширяете их. Тогда вы бы подали заявку Breadth-first search чтобы не пересекать те же самые пути снова и использовать ранее вычисленные общие расстояния. Алгоритм, на мой взгляд, немного сложен, извините, но не хватает времени, чтобы написать его.