Estoy tratando de resolver este problema de Leetcode: Binary Tree Maximum Path Sum. Sé que hay muchas respuestas SO para esta pregunta. Pero no pude encontrar nada relacionado con mi problema. Entonces, antes de sumergirme en el código, quiero dar una descripción general de alto nivel de cómo escribí el algoritmo.
If I am at a particular node, I considered the following cases. Case 1: The maximum path is somewhere inside the left subtree (not including the current node) Case 2: The maximum path is somewhere inside the right subtree (not including the current node) Case 3: The maximum path starts from the current node and ends somewhere in the left subtree Case 4: The maximum path starts from the current node and ends somewhere in the right subtree Case 5: The maximum path is the current node itself. Case 6: The maximum path starts somewhere in the left subtree, goes through the current node, and ends somewhere in the right subtree.Y aquí está el código:
var maxPathSum = function(root) { if (root.left === null && root.right === null) { return root.val; } // Case 1: Max sum is in the left subtree (not including the root) let leftPathSum = 0; if (root.left) { leftPathSum = maxPathSum(root.left); } // Case 2: Max sum is in the right subtree (not including the root) let rightPathSum = 0; if (root.right) { rightPathSum = maxPathSum(root.right); } // Case 3: root + leftPathSum let leftSumWithRoot = leftPathSum + root.val; // Case 4: root + rightPathSum let rightSumWithRoot = rightPathSum + root.val; let maxWithRoot = Math.max(leftSumWithRoot, rightSumWithRoot); let maxWithoutRoot = Math.max(leftPathSum, rightPathSum); let maxSoFar = Math.max(maxWithRoot, maxWithoutRoot); // Case 5: Root with alone maxSoFar = Math.max(maxSoFar, root.val); // Case 6: Max path goes through the root let maxThroughRoot = leftSumWithRoot + rightSumWithRoot - root.val; return Math.max(maxThroughRoot, maxSoFar); };Estoy pasando algunos de los casos de prueba, otros no, especialmente los que tienen valores negativos. Sé que mi algoritmo probablemente tenga problemas, pero ¿alguien puede ayudarme si mi pensamiento va en la dirección equivocada? Vi diferentes soluciones a este problema. En algunas soluciones, comparan maxPathSum (nodo. izquierda) y maxPathSum (nodo. derecha) con 0. ¿El problema está relacionado con esto? Además, en algunas otras soluciones, no están considerando maxPathSum que está dentro del subárbol izquierdo y derecho. ¿No debería hacer eso? Si alguien me da una idea de dónde estoy haciendo mal, estaría muy agradecido. Gracias por adelantado.
Tu código está fallando en esta entrada: [-2,-1]
gráfico se ve así:
-2 / -1 Entonces, let maxWithoutRoot = Math.max(leftPathSum, rightPathSum); será 0. Entonces maxSoFar será cero, por lo que eventualmente su salida será 0. Si organizo su código:
var maxPathSum = function(root) { let res=root.val function dfs(node){ if (node===null){ return 0 } let left=dfs(node.left) let right=dfs(node.right) // ignoring negatives. looking for max, so if left or right is negative, do not add it let leftMax=Math.max(left,0) let rightMax=Math.max(right,0) res=Math.max(node.val+leftMax+rightMax,res) return node.val+Math.max(leftMax,rightMax) } dfs(root) return res };