Caminos en un árbol binario con suma dada
Los árboles binarios se pueden representar con el de tipo de dato algebraico
data Arbol = H | N Int Arbol Arbol deriving Show
Por ejemplo, los árboles
3 7 1
/ \ / \ / \
2 4 5 8 / \
/ \ \ / / \ / \
1 7 5 6 4 9 3 -1
/ \ / \
2 1 4 5
/ / \ \
1 1 2 6
se representan por
ej1, ej2, ej3 :: Arbol ej1 = N 3 (N 2 (N 1 H H) (N 7 H H)) (N 4 H (N 5 H H)) ej2 = N 7 (N 5 (N 6 H H) H) (N 8 (N 4 H H) (N 9 H H)) ej3 = N 1 (N 3 (N 2 H H) (N 1 (N 1 H H) H)) (N (-1) (N 4 (N 1 H H) (N 2 H H)) (N 5 H (N 6 H H)))
Definir las funciones
caminos :: Arbol -> [[Int]] caminosSuma :: Arbol -> Int -> [[Int]]
tales que
- (caminos a) es la lista de los caminos entre dos nodos cualesquiera del árbol a. Por ejemplo,
λ> caminos ej1 [[3],[3,2],[3,2,1],[3,2,7],[3,4],[3,4,5], [2],[2,1],[2,7],[1],[7],[4],[4,5],[5]] λ> caminos ej2 [[7],[7,5],[7,5,6],[7,8],[7,8,4],[7,8,9], [5],[5,6],[6],[8],[8,4],[8,9],[4],[9]] λ> length (caminos ej3) 33
- (caminosSuma a k) es la lista de los caminos entre dos nodos cualesquiera del árbol a cuya suma es k. Por ejemplo,
λ> caminosSuma ej1 3 [[3],[2,1]] λ> caminosSuma ej3 3 [[3],[-1,4]] λ> caminosSuma ej3 4 [[1,3],[1,-1,4],[3,1],[-1,4,1],[-1,5],[4]] λ> caminosSuma ej3 5 [[1,3,1],[1,-1,4,1],[1,-1,5],[3,2],[3,1,1],[-1,4,2],[4,1],[5]] λ> caminosSuma ej3 6 [[1,3,2],[1,3,1,1],[1,-1,4,2],[4,2],[6]] λ> caminosSuma ej3 7 []
Soluciones
data Arbol = H | N Int Arbol Arbol deriving Show ej1, ej2, ej3 :: Arbol ej1 = N 3 (N 2 (N 1 H H) (N 7 H H)) (N 4 H (N 5 H H)) ej2 = N 7 (N 5 (N 6 H H) H) (N 8 (N 4 H H) (N 9 H H)) ej3 = N 1 (N 3 (N 2 H H) (N 1 (N 1 H H) H)) (N (-1) (N 4 (N 1 H H) (N 2 H H)) (N 5 H (N 6 H H))) caminos :: Arbol -> [[Int]] caminos H = [] caminos a@(N r i d) = caminosDesdeRaiz a ++ caminos i ++ caminos d -- (caminosDesdeRaiz a) es la lista de las caminosDesdeRaiz desde la -- raíz de a hasta cualquiera de sus nodos. Por ejemplo. -- λ> caminosDesdeRaiz ej1 -- [[3],[3,2],[3,2,1],[3,2,7],[3,4],[3,4,5]] -- λ> caminosDesdeRaiz ej2 -- [[7],[7,5],[7,5,6],[7,8],[7,8,4],[7,8,9]] caminosDesdeRaiz :: Arbol -> [[Int]] caminosDesdeRaiz H = [] caminosDesdeRaiz (N x i d) = [x] : [x:ys | ys <- caminosDesdeRaiz i ++ caminosDesdeRaiz d] caminosSuma :: Arbol -> Int -> [[Int]] caminosSuma a k = [ys | ys <- caminos a , sum ys == k]
Referencia
Basado en Print all k-sum paths in a binary tree de GeeksforGeeks.