189 lines
3.3 KiB
Python
Executable File
189 lines
3.3 KiB
Python
Executable File
#!/usr/bin/env python
|
|
"""
|
|
Suma Mayor de rutas
|
|
|
|
Escribe una función, SumaRutaMasLarga, que reciba la raíz
|
|
de un árbol binario que contenga números.
|
|
La función debe retornar la suma mayor de todas las rutas
|
|
raiz-hoja (root-leaf) del árbol.
|
|
Se asume que el árbol no esta vacío
|
|
"""
|
|
|
|
from arbol_binario import Nodo, SumaMayorDeRutas, SumaMayorDeRutas2
|
|
import unittest
|
|
import TestRunner
|
|
|
|
|
|
def test_00():
|
|
"""
|
|
3
|
|
/ \\
|
|
11 4
|
|
/ \ \\
|
|
4 -2 1
|
|
max_path_sum(a) # -> 18
|
|
"""
|
|
a = Nodo(3)
|
|
b = Nodo(11)
|
|
c = Nodo(4)
|
|
d = Nodo(4)
|
|
e = Nodo(-2)
|
|
f = Nodo(1)
|
|
a.left = b
|
|
a.right = c
|
|
b.left = d
|
|
b.right = e
|
|
c.right = f
|
|
return SumaMayorDeRutas(a)
|
|
|
|
def test_01():
|
|
"""
|
|
5
|
|
/ \\
|
|
11 54
|
|
/ \
|
|
20 15
|
|
/\\
|
|
1 3
|
|
max_path_sum(a) # -> 59
|
|
"""
|
|
a = Nodo(5)
|
|
b = Nodo(11)
|
|
c = Nodo(54)
|
|
d = Nodo(20)
|
|
e = Nodo(15)
|
|
f = Nodo(1)
|
|
g = Nodo(3)
|
|
a.left = b
|
|
a.right = c
|
|
b.left = d
|
|
b.right = e
|
|
e.left = f
|
|
e.right = g
|
|
return SumaMayorDeRutas(a)
|
|
|
|
def test_02():
|
|
"""
|
|
-1
|
|
/ \\
|
|
-6 -5
|
|
/ \ \\
|
|
-3 0 -13
|
|
/ \\
|
|
-1 -2
|
|
max_path_sum(a) # -> -8
|
|
"""
|
|
a = Nodo(-1)
|
|
b = Nodo(-6)
|
|
c = Nodo(-5)
|
|
d = Nodo(-3)
|
|
e = Nodo(0)
|
|
f = Nodo(-13)
|
|
g = Nodo(-1)
|
|
h = Nodo(-2)
|
|
a.left = b
|
|
a.right = c
|
|
b.left = d
|
|
b.right = e
|
|
c.right = f
|
|
e.left = g
|
|
f.right = h
|
|
return SumaMayorDeRutas(a)
|
|
|
|
def test_03():
|
|
"""
|
|
42
|
|
max_path_sum(a) # -> 42
|
|
"""
|
|
a = Nodo(42)
|
|
return SumaMayorDeRutas(a)
|
|
|
|
|
|
class SumaMayorDeRutasTestCase1(unittest.TestCase):
|
|
|
|
def test_suma_mayor_de_rutas_00(self):
|
|
self.assertEqual(18, test_00())
|
|
|
|
def test_suma_mayor_de_rutas_01(self):
|
|
self.assertEqual(59, test_01())
|
|
|
|
def test_suma_mayor_de_rutas_02(self):
|
|
self.assertEqual(-8, test_02())
|
|
|
|
def test_suma_mayor_de_rutas_03(self):
|
|
self.assertEqual(42, test_03())
|
|
|
|
|
|
def test_10():
|
|
a = Nodo(3)
|
|
b = Nodo(11)
|
|
c = Nodo(4)
|
|
d = Nodo(4)
|
|
e = Nodo(-2)
|
|
f = Nodo(1)
|
|
a.left = b
|
|
a.right = c
|
|
b.left = d
|
|
b.right = e
|
|
c.right = f
|
|
return SumaMayorDeRutas2(a)
|
|
|
|
def test_11():
|
|
a = Nodo(5)
|
|
b = Nodo(11)
|
|
c = Nodo(54)
|
|
d = Nodo(20)
|
|
e = Nodo(15)
|
|
f = Nodo(1)
|
|
g = Nodo(3)
|
|
a.left = b
|
|
a.right = c
|
|
b.left = d
|
|
b.right = e
|
|
e.left = f
|
|
e.right = g
|
|
return SumaMayorDeRutas2(a)
|
|
|
|
def test_12():
|
|
a = Nodo(-1)
|
|
b = Nodo(-6)
|
|
c = Nodo(-5)
|
|
d = Nodo(-3)
|
|
e = Nodo(0)
|
|
f = Nodo(-13)
|
|
g = Nodo(-1)
|
|
h = Nodo(-2)
|
|
a.left = b
|
|
a.right = c
|
|
b.left = d
|
|
b.right = e
|
|
c.right = f
|
|
e.left = g
|
|
f.right = h
|
|
return SumaMayorDeRutas2(a)
|
|
|
|
def test_13():
|
|
a = Nodo(42)
|
|
return SumaMayorDeRutas2(a)
|
|
|
|
|
|
class SumaMayorDeRutasTestCase2(unittest.TestCase):
|
|
|
|
def test_suma_mayor_de_rutas_10(self):
|
|
self.assertEqual(18, test_10())
|
|
|
|
def test_suma_mayor_de_rutas_11(self):
|
|
self.assertEqual(59, test_11())
|
|
|
|
def test_suma_mayor_de_rutas_12(self):
|
|
self.assertEqual(-8, test_12())
|
|
|
|
def test_suma_mayor_de_rutas_13(self):
|
|
self.assertEqual(42, test_13())
|
|
|
|
|
|
if __name__ == '__main__':
|
|
TestRunner.main()
|
|
#unittest.main()
|
|
|