Общее время посещения всех узлов бинарного дерева

Учитывая бинарное дерево, найдите общее время посещения всех узлов от корневого узла. Посещение дочернего узла с его родительского узла будет стоить 1 единицу времени, а посещение родителя с дочернего узла вызовет 0 единиц времени.

Примеры:

Input: 

Output: 5
Explanation: The traversals taking 1 unit of time are 1->2, 2->4, 4->5, 1->3 and 3->6.

Input: 

Output: 1

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

Общее время посещения всех узлов бинарного дерева, если известно количество узлов (N) : Если количество узлов в бинарном дереве уже известно как N , то количество ребер в нем равно N-1 . Таким образом, ответ N-1 в этом случае.

Временная сложность: O(1)
Вспомогательное пространство: O(1)

Общее время посещения всех узлов бинарного дерева, если количество узлов неизвестно: Примените поиск в глубину, чтобы получить количество ребер и вернуть его в качестве ответа. Теперь выполните следующие шаги, чтобы решить эту проблему:

1. Создайте рекурсивную функцию totalTime , которая примет узел в качестве параметра и вернет количество ребер под ним.
2. Итак, получите количество ребер в левом потомке, вызвав функцию totalTime для левого потомка и добавив к ней единицу.
3. Повторите вышеуказанный шаг для правого ребенка.
4. В конце верните сумму ребер слева и справа.
5. Выведите ответ в соответствии с описанным выше подходом.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(V), где V — количество узлов бинарного дерева.
Вспомогательное пространство: O(1)