Получение средней высоты бинарного дерева поиска

Question

я пришел к постановке задачи, где дерево находится в форме:

 4 
    2  6 
1 3 5 7 

Он сказал, что средняя высота составляет 1,4285715

Исходя из чего я знаете, средняя высота дерева - это сумма высоты каждого узла, деленная на общее количество узлов. Однако я получаю другой результат. Мне нужен намек на то, как вычисляется значение 1.4285715.

Answer 1

Используйте вашу формулу ans set глубину корня до 0: (0 + 1 + 1 + 2 + 2 + 2 + 2)/7 = 10/7 = 1.4285715.

Answer 2

Корневой узел обычно не включен в высоту, хотя он включен при подсчете узлов. Таким образом, мы имеем два узла высоты 1 и четыре узла высоты 2:

(2 * 1) + (4 * 2) = 10 
10/7   = 1.4285714286 

Подробнее на http://en.wikipedia.org/wiki/Binary_tree

Answer 3

 4  // 0 
    2  6  // 1 
1 3 5 7 // 2 

(0 + 1 + 1 + 2 + 2 + 2 + 2)/7 = 1.4285715