Как найти максимальную сумму пути между любыми двумя узлами в bst?

-1

Как мы можем найти максимально возможную сумму пути между любыми двумя элементами в дереве двоичного поиска? Я не просто говорю о каких-либо двух листовых узлах. Этот вопрос включает все узлы. И по сумме пути я подразумеваю сумму всех элементов данных в пути.Как найти максимальную сумму пути между любыми двумя узлами в bst?

источник

2015-06-28 Sarin Nanda

Можете ли вы описать путь? Вы имеете в виду «цепочку родителей»? – Amit

Путь означает расстояние от одного узла к другому. И сумма пути означает сумму элементов данных в пути. –

Возможно, я не понимаю вопрос, но путь должен включать только уникальные узлы, потому что если бы не ответ был бы бесконечным. Если это уникально, не будет ли max равным min? –

Использование псевдо-код:

Set maxSum = MINVALUE 

TreeMaxSum (tree) 
    maxLeft = TreeMaxSum(tree->left) 
    maxRight = TreeMaxSum(tree->right) 
    maxSum = max(maxSum, maxLeft+maxRight+tree->value) 
    return max(maxLeft, maxRight) + tree->value 

TreeMaxSum(tree)

Конечно, вы должны заботиться о обычных случаях края и значения «пустой лист» ...

источник

2015-06-28 18:10:12 Amit

Как найти максимальную сумму пути между любыми двумя узлами в bst?

ответ

Смежные вопросы