Учитывая полное двоичное дерево (у каждого узла есть 1 левый и 1 правый дочерний), напишите алгоритм для печати всех путей от корня к листу.
Вот рекурсивный алгоритм в Python:
def print_tree(root):
dfs(root, '')
def dfs(root, path):
path += root.value
if not root.right and not root.left:
print path
return
if root.left:
dfs(root.left,path)
if root.right:
dfs(root.right,path)
Грубый анализ сложности пространства:
O (log (N)) в кадре стека (максимальное количество рекурсивных вызовов - глубина дерева)
O (log (N)) в куче (максимальное количество строковых конструкций также является глубиной дерева, данный путь является строкой, которая неизменна в питоне).
Более сложный вопрос: опишите общее использование памяти на листовом узле.
Итак, на листовом узле у нас будет журнал (N) указателей на функции в стеке вызовов. Но сколько «копий» или выделений памяти существует для path? Я утверждаю, что есть также log (N) таких копий, так как путь не собирается сборщиком мусора до тех пор, пока не будет возвращена каждая вызывающая функция.
Итак, на конечном узле у нас есть log (N) + log (N) общей сложности памяти. Это точно?