Максимальная сумма путей между двумя конечными узлами (GeeksForGeeks) ⇐ Python

[Anonymous]

Дано двоичное дерево, в котором каждый элемент узла содержит число. Найдите максимально возможную сумму от одного листового узла до другого.
Пример 1:

Код: Выделить всё

Input :
3
/    \
4       5
/  \
-10   4

Output: 16

Объяснение:
Максимальная сумма находится между листовыми узлами 4 и 5.
4 + 4 + 3 + 5 = 16.
Пример 2:

Код: Выделить всё

Input :
-15
/      \
5         6
/  \       / \
-8    1     3   9
/  \              \
2   -3              0
/ \
4  -1
/
10

Output :  27

Объяснение:
Максимально возможная сумма от одного листового узла
до другого равна (3 + 6 + 9 + 0 + -1 + 10 = 27)
Объяснение:
Максимально возможная сумма от одного листового узла
до другого равна (3 + 6 + 9 + 0 + -1 + 10 = 27)
p>
Это решение:

Код: Выделить всё

'''
# Node Class:
class Node:
def _init_(self,val):
self.data = val
self.left = None
self.right = None
'''
res = -999999999
def maxPathSumUtil(root):
global res
if root is None:
return 0

if root.left is None and root.right is None:
return root.data

ls=maxPathSumUtil(root.left)
rs=maxPathSumUtil(root.right)

if root.left and root.right:
res=max(res,ls+rs+root.data)
return max(ls+root.data,rs+root.data) #Line: Problem
if root.left is None:
return rs+root.data
else:
return ls+root.data

def maxPathSum(root):
global res
res = -999999999
maxPathSumUtil(root)
return res

Может кто-нибудь сказать мне, почему мы используем return max(ls+root.data,rs+root.data). И если мы используем return max(ls+root.data,rs+root.data) для проверки максимального значения, то почему мы используем res=max(res,ls+rs+root.data), а не просто res = max(ls+root.data,rs+root.data).
РЕДАКТИРОВАТЬ:
Например:

Код: Выделить всё

Let's take this tree for example:

10
/   \
8      2
/  \
3     5

При этом после рекурсивных вызовов ls становится равным 3, а rs становится равным 5.

Код: Выделить всё

res

становится ls+rs+root.data, что равно 3+5+8 = 16.
Затем верните max(ls+root.data,rs+root.data) то есть max(11,13) = 13.
Теперь, по моему мнению, после этого функция должна просто вернуть 13, но этого не происходит. Несмотря на то, что return не является рекурсивным оператором. Как происходит поток управления кодом?

Подробнее здесь: https://stackoverflow.com/questions/646 ... ksforgeeks