Dado un árbol binario, encuentre la suma máxima de la ruta. La ruta puede comenzar y terminar en cualquier nodo del árbol. Por ejemplo, dado el siguiente árbol binario
1
/
2 3
el resultado es 6.
Análisis
1) Resuelve este problema de forma recursiva
2) Obtenga la mayor suma izquierda y derecha
2) Compare con el máximo almacenado
Solución Java
También podemos usar una matriz para almacenar valor para métodos recursivos.
public int maxPathSum(TreeNode root) { int max[] = new int[1]; max[0] = Integer.MIN_VALUE; calculateSum(root, max); return max[0]; } public int calculateSum(TreeNode root, int[] max) { if (root == null) return 0; int left = calculateSum(root.left, max); int right = calculateSum(root.right, max); int current = Math.max(root.val, Math.max(root.val + left, root.val + right)); max[0] = Math.max(max[0], Math.max(current, left + root.val + right)); return current; } |
