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

#java #tree #binary-search-tree

#java #дерево #binary-search-tree

Вопрос:

Недавно меня спросили об этом в интервью и поставили в тупик.

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

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

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

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

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

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

Ответ №1:

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

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

Псевдокод Java-ish может быть:

 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
}

Может потребоваться некоторая специальная обработка для пустого дерева..

Ответ №2:

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

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