Какова сумма двоичного дерева с заданными корневым и целевым узлами?

Question

У меня есть двоичное дерево в качестве входных данных функции. У меня есть корень дерева и 2 узла. Мне нужно вычислить сумму вдоль пути между двумя заданными узлами.

Пример дерева:

     4
   /   \
  8    13
 / \
24 45

Код:

List<Node> findPath(root, target):
if (root !=null)
    return
if root == node{
    return nodes.add(target)
}
path = findPath(root.left, target)
if (path !=null){
    return nodes.add(root).addAll(path)
}
path = findPath(root.right, target)
if (path!=null)
      return nodes.add(root).addAll(path)

Я не знаю, каким будет следующий шаг, если у меня есть пути к целевым узлам, как мне рассчитать оптимальный путь?

Input: sumTree(4, 24, 45)
Output: 8 + 24 + 45 = 77

Input: sumTree(4, 24, 13)
Output: 13 + 4 + 8 + 24 = 49

Input: sumTree(4, 4, 13)
Output: 4 + 13 = 17

Input: sumTree(4, 45, 45)
Output: 45

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

Answer 1

Ваши два пути будут иметь одинаковый префикс (по крайней мере, корень должен быть там).Вам нужно удалить общий префикс и добавить только последний (самый глубокий) общий узел (один раз).Для частей, которые отличаются, вам нужно добавить все значения.Это должно быть O(N) сложность и соответствовать остальной части решения.

Ваш алгоритм поиска неэффективен, потому что вы продолжаете копировать значения из одного списка в другой (O(N^2), если вы нене имеет никаких ограничений на дерево).Если вы измените его, чтобы построить ответ на месте, он должен стать O(N).