Вычисление глубины дерева в Python

Question

Определите функцию sum_to_deepest(root), которая возвращает сумму ключей от корня до самого глубокого листа в дереве, корневом в корне. Если есть два самых глубоких листа, верните большую сумму; если корень равен None, верните 0.

В этой проблеме вы обнаружите, что это помогает определить вспомогательную функцию, которая возвращает как глубину самого глубокого листа, так и сумму по пути к этому листу.

Answer 1

Вы должны действительно не просите об этом здесь для ответа. Сначала попробуйте что-нибудь. Я дам вам только подсказки и псевдокод.

Узел имеет атрибуты left, right, key.

Для расчета высоты вы можете сделать это рекурсивно. Вам нужно взять больше высоты левого и правого поддеревьев и добавить 1.

Представьте

A 
/\ 
    B C 
/
D 

псевдокод:

height(node)-> 
    if(node is a leaf) return 0 
    return maximum(height(left subtree), height(right subtree)) + 1 

Начиная с А,

height(A) -> maximum(height(B), height(C) + 1 
height(B) -> maximum(height(D), null) + 1 
height(D) -> 0 
height(B) -> 1 
height(C) -> 0 
height(A) -> maximum(1, 0) + 1 = 2 

Чтобы получить сумму, вам необходимо определить, какой путь по дереву собирается доставить вас до самого глубокого l т.в.ф.. Высота самого глубокого листа будет по пути поддерева с большей высотой, поэтому что-то вроде этого (псевдокод):

sum_to_deepest(node) -> 
    if(node is null) return 0 
    leftheight = height(left subtree) 
    rightheight = height(right subtree) 
    if(leftheight > rightheight) then 
     return (current key) + sum_to_deepest(left subtree) 
    return (current key) + sum_to_deepest(right subtree)