Вопрос:
Я пришел к описанию проблемы, где дерево находится в форме:
4 2 6 1 3 5 7
Он сказал, что средняя высота 1.4285715
Исходя из того, что я знаю, средняя высота дерева – это сумма высоты каждого узла, деленная на общее количество узлов. Однако я получаю другой результат. Мне нужен намек на то, как вычисляется значение 1.4285715.
Лучший ответ:
Используйте свою формулу ans set глубину корня до 0: (0 + 1 + 1 + 2 + 2 + 2 + 2)/7 = 10/7 = 1.4285715.
Ответ №1
Корневой узел обычно не включается в высоту, хотя он включен при подсчете узлов. Итак, у нас есть два узла высоты 1 и четыре узла высотой 2:
(2 * 1) + (4 * 2) = 10 10 / 7 = 1.4285714286
Читайте больше на http://en.wikipedia.org/wiki/Binary_tree
Ответ №2 4 // 0 2 6 // 1 1 3 5 7 // 2 (0 + 1 + 1 + 2 + 2 + 2 + 2) / 7 = 1.4285715
