Наименьший путь значения в двоичном дереве поиска

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

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

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

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

источник

2016-10-05 samz_manu

Я предполагаю, что это будет включать какой-то цикл, как таковой, что, если у вас есть список, который хранит каждое значение для каждой итерации dfs? Как только он пересечет все узлы, вы можете просто захватить самую большую. Я помню, что мне нужно было знать, как найти это в моем классе структур данных, это было на C++, и я не могу сейчас вспомнить. – SomeStudent

Просто используйте рекурсивную реализацию, и стек «проведет» все необходимые вам данные. Но, идя таким образом, вы гарантируете полный обход, что является неоптимальным. Использование обхода BFS может остановить определенные пути в середине, но это сложнее в дизайне. – Amit

Вещь с dfs - она дойдет до конца и вернется обратно и найдет следующий неустановленный узел. Но мне нужно знать сумму на узле, который он расходится, чтобы найти следующий неустановленный узел, если я должен записать его как новый путь. Трудно объяснить словами, которые я предполагаю, но в основном dfs не работает, если не реализована некоторая умная память для запоминания в определенных узлах. –

Это можно решить по этим строкам: представьте, что мы определяем функцию lowestValuePath(path, currentValue, bst), которая берет путь в виде строкового представления («lrlrr» будет эквивалентно тому, что он прошел влево, вправо, влево, вправо, вправо), значение который представляет собой накопленную в настоящее время сумму значений узлов вдоль этого пути, а bst - дерево для перемещения.

Наш пусковой корпус будет lowestValuePath("", 0, rootNode), и прекращение будет происходить на листе, возвращая пройденный путь и значение, накопленное вдоль этого пути.

Java-МОГ псевдо-код может быть:

TraverseResult { 
    String path; 
    int value; 
} 

TraverseResult lowestValuePath(path, currentValue, bst) { 
    val newValue = currentValue + bst.getNodeValue(); 
    if bst.isLeaf(): 
    return new TraverseResult(path, newValue); 
    else 
    val rightPath = lowestValuePath(path + "r", newValue, bst.getRightNode()); 
    val leftPath = lowestValuePath(path + "l", newValue, bst.getLeftNode()); 
    return leftPath < rightPath ? leftPath : rightPath 
}

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

источник

2016-10-05 22:18:11

Если это «Двоичное дерево», то для каждого узла T: левый (T) < = T < = правый (T)

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

источник

2016-10-05 22:20:06

Это не сработает, если дерево не сбалансировано. –

Не обязательно быть двоичным деревом поиска. –

Наименьший путь значения в двоичном дереве поиска

ответ

Смежные вопросы