Эту проблему можно решить с помощью рекурсивной функции, которая возвращает длину пути от текущего узла до начального узла (или просто самый длинный путь к любому листу, если начальный узел не находится под ним).
Мы также можем заставить его вернуть самый длинный путь до исходного узла, если он найден, который является просто суммой функции, вызываемой как для левого, так и для правого потомка (плюс один, для текущего узла).
Это похоже на решение, описанное m69 .
Это выполняется за O (n) времени, так как функция выполняется в постоянное время (если исключить рекурсивные вызовы),и функция вызывается не более трех раз для каждого узла (для самого узла и для его левого и правого потомков, в случае конечных узлов).
Это будет использовать пространство O (высота), так как мымы ничего не храним, кроме вызовов функций с их переменными, а максимальное количество тех, которые мы можем иметь в памяти в любой момент времени, равно глубине рекурсии (т.е.высота дерева).
class Node:
def __init__(self, key):
self.left = None
self.right = None
self.value = key
# returns a tuple (max = the longest path so far, dist = current path)
def _recurse(node, start):
if node is None:
return (None, 0)
else:
max_left, dist_left = _recurse(node.left, start)
max_right, dist_right = _recurse(node.right, start)
# this node is the starting node
if node == start:
return (0, 0)
# the starting node is in left or right
elif max_right is not None or max_left is not None:
return (dist_right + dist_left + 1,
(dist_left if max_right is None else dist_right) + 1)
# we haven't seen the starting node
else:
return (None, max(dist_left, dist_right) + 1)
def time_to_burn(root, start):
return _recurse(root, start)[0]
Тест:
root = Node(1)
root.left = Node(1)
root.right = Node(1)
root.left.left = Node(1)
root.left.right = Node(1)
root.left.right.left = Node(1)
root.left.right.right = Node(1)
root.right.right = Node(1)
root.right.right.right = Node(1)
root.right.right.right.right = Node(1)
>>> time_to_burn(root, root.left.right.right)
7
Решение, которое работает с неконцевыми начальными узлами
Основная идея состоит в том, чтобы иметь 3 возвратазначения для каждого узла:
max, который является самым длинным путем от начального узла, полученным до сих пор (или None, если мы еще не видели начальный узел). above, то есть число узлов выше начального узла (или None, если мы еще не видели начальный узел). below, который является самым длинным путем ниженачальный узел (или просто самый длинный путь от текущего узла, если мы еще не видели начальный узел).
Вычисление above и below из дочерних поддеревьев довольно прямолинейно.вперед - подробности см. в коде.
Мы можем определить самый длинный путь max от текущего узла как максимум:
- Самый длинный путь, идущий вниз от начального узла(это просто
below) - и самый длинный путь, который включает в себя текущий узелe, которое будет расстоянием от текущего узла до начального узла плюс самый длинный путь в поддереве без начального узла (плюс один).
Код: (заменяя функцию _recurse выше)
# returns a tuple (max, above, below)
def _recurse(node, start):
if node is None:
return (None, None, 0)
else:
max_left, above_left, below_left = _recurse(node.left, start)
max_right, above_right, below_right = _recurse(node.right, start)
# this node is the starting node
if node == start:
below = max(below_left, below_right)
return (below, 0, below)
# the starting node is in left or right
elif above_right is not None or above_left is not None:
return (max((0 if above_right is None else above_right) + below_left,
(0 if above_left is None else above_left) + below_right) + 1,
(above_right if above_left is None else above_left) + 1,
below_right if above_left is None else below_left)
# we haven't seen the starting node
else:
return (None, None, max(below_left, below_right) + 1)
>>> time_to_burn(root, root.left.right)
6