tema:
Suma máxima de ruta del árbol binario
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 árbol binario a continuación,
1 / / 2 3
Regresar 6.
El nodo puede ser negativo, buscando una ruta más para que los nodos pasados sean los más grandes. La ruta puede comenzar y terminar en cualquier nodo, pero no puede regresar.
Aunque esta pregunta parece inusual, si lo piensas, encontrarás que no es más que recorrer árboles binarios + ideas simples de planificación dinámica.
Podemos separar el problema: incluso si la última ruta más grande no pasa a través del nodo raíz, debe tener su propio "punto más alto". Por lo tanto, solo necesitamos averiguar todos los nodos: si la ruta toma este nodo como el "punto más alto", ¿cuál es la longitud máxima de la ruta? Nota como max. Luego encuentre el valor máximo máximo en Max, que es el resultado que está buscando. La misma idea que "encontrar la mayor subsecuencia continua en una secuencia entera".
Lo siguiente es encontrar la relación entre Max correspondiente a cada "punto más alto".
Tomemos el nodo raíz como ejemplo. El método de cálculo para la ruta máxima que pasa a través del nodo raíz es:
Encontramos la longitud máxima de la ruta A en el subárbol izquierdo con el niño izquierdo como punto de partida, y la longitud máxima de la ruta B en el subárbol derecho con el niño derecho como punto de partida. Entonces el max = max de este punto (a+b+node.val, a+node.val, b+node.val, node.val)
Por lo tanto, definimos una función para calcular A o B arriba. Su parámetro es un nodo, y su valor de retorno es la longitud máxima de la ruta. Sin embargo, el punto de partida de esta ruta debe ser el nodo de entrada, y la ruta debe estar en un subárbol con el punto de partida como nodo raíz.
Entonces el valor de retorno de la función func (nodo) se puede definir de la siguiente manera: returnmax (func (node.left)+node.val, func (node.right)+node.val, node.val)
La condición de terminación es nodo == NULL, y devuelve 0 directamente.
Luego encontramos que el proceso anterior de calcular a Max y calcular a Max puede ponerse completamente en func (nodo).
Según el código de esta idea, MaxPathSumCore es la implementación anterior de FUNC (nodo):
/** * Definición para el árbol binario * struct treeNode { * int val; * TreeNode * izquierda; * TreeNode * derecho; * TreeNode (int x): val (x), izquierda (nulo), derecha (nulo) {} *}; */class Solution {public: int maxPathSum (treeNode *root) {maxPathSumCore (root); return max;} int maxPathSumCore (treeNode *node) {if (null == nodo) return 0; int a = maxpathSumCore (node -> izquierdo); int b = maxpathsumcore (nodo (nodo -nodo; derecho); if ((a+b+nodo-> val)> max) max = (a+b+nodo-> val); if ((a+nodo-> val)> max) max = (a+nodo-> val); if ((b+nodo-> val)> max) max = (b+nodo-> val); if (node-> val> max) max = node-> val) maxViAtHisNode = ((a + nodo-> val)> nodo-> val? (a + nodo-> val): nodo-> val); return (maxViAthisNode> (b + node-> val)? maxViAthItSnode: (b + node-> val));} privado: int max = -9999999999999999999999999;};Complejidad del tiempo o (n), n es el número total de nodos.
Resumir
Lo anterior es todo el contenido de este artículo sobre el análisis del código de la ruta máxima del árbol binario en la programación de Java. Espero que sea útil para todos. Los amigos interesados pueden continuar referiéndose a otros temas relacionados en este sitio. Si hay alguna deficiencia, deje un mensaje para señalarlo. ¡Gracias amigos por su apoyo para este sitio!