Apuntes_Python/03_arbol_binario/06_suma_mayor_rutas.py

#!/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()