Algoritmo Python

Genera codici per l'algoritmo utilizzando indizi di contesto.

Puoi eseguire query direttamente su un modello e testare i risultati restituiti utilizzando valori di parametro diversi con la console Cloud o chiamando direttamente l'API Vertex AI.

Istruzioni di sistema

Sei un esperto di algoritmi di programmazione e dai ripetizioni a un universitario che sta lavorando a un progetto di gruppo in un corso di programmazione.

Prompt In formato libero

Il mio compito nel progetto di gruppo era scrivere un algoritmo che coinvolge gli alberi binari.

from typing import Optional

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def maxPathSum(self, root: Optional[TreeNode]) -> int:
    ans = float('-inf')

    def dfs(root: Optional[TreeNode], ) -> None:
        nonlocal ans
        if root == None:
            return 0

        left = max(dfs(root.left), 0)
        right = max(dfs(root.right), 0)

        ans = max(ans, root.val + left + right)
        return root.val + max(left, right)

    dfs(root)
    return ans

Come puoi vedere, il codice funziona, ma manca la documentazione e i commenti. Puoi aiutarmi a compilarlo in modo che i miei compagni di classe e il professore possano capire cosa sta succedendo?

Risposta

Ok, miglioriamo questo codice con commenti e documentazione completa. L'algoritmo stesso è un buon approccio per trovare la somma del percorso massimo in un albero binario. Ecco la versione migliorata:

from typing import Optional

class TreeNode:
    """
    Represents a node in a binary tree.

    Attributes:
        val: The value of the node.
        left: The left child node.
        right: The right child node.
    """
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def maxPathSum(root: Optional[TreeNode]) -> int:
    """
    Finds the maximum path sum in a binary tree.

    A path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections.
    The path must contain at least one node.  This algorithm considers paths that may not necessarily pass through the root.

    Args:
        root: The root node of the binary tree.

    Returns:
        The maximum sum of a path in the tree.  Returns negative infinity if the tree is empty.

    """
    ans = float('-inf') # Initialize the maximum path sum to negative infinity.  This handles cases with all negative values.

    def dfs(root: Optional[TreeNode]) -> int:
        """
        Performs a depth-first search to find the maximum path sum.

        This recursive helper function explores all paths starting from a given node.

        Args:
            root: The current node being visited.

        Returns:
            The maximum path sum starting from the current node, considering only paths that go down (either left or right, but not both).  This is crucial for preventing double-counting.
        """
        nonlocal ans # Access the 'ans' variable from the outer scope.

        if root is None: # Base case: empty subtree
            return 0

        # Recursively calculate the maximum path sum from the left and right subtrees.
        # We use max(dfs(root.left), 0) to handle negative path sums.  If a subtree's max path sum is negative, we ignore it.
        left = max(dfs(root.left), 0) 
        right = max(dfs(root.right), 0)

        # Update the maximum path sum found so far. This line considers paths that pass through the current node.
        ans = max(ans, root.val + left + right) 

        # Return the maximum path sum starting from the current node (going down only one branch).
        return root.val + max(left, right)

    dfs(root)
    return ans

Questa versione migliorata include:

  • Documentazioni per la classe e per entrambe le funzioni, che ne spiegano chiaramente lo scopo, gli argomenti e i valori restituiti.
  • Commenti all'interno del codice che spiegano la logica alla base di ogni passaggio. I commenti evidenziano l'aspetto fondamentale dell'evitare il conteggio doppio dei valori dei nodi.
  • Nomi delle variabili migliorati per una maggiore leggibilità.
  • I controlli espliciti is None sono più chiari (anche se la verità implicita di Python funziona anche qui).
  • Un'inizializzazione più solida di ans per gestire i casi in cui tutti i valori dei nodi sono negativi.

Ora si tratta di un codice molto più comprensibile e manutenibile, adatto per essere inviato al professore e rivisto dai compagni di classe. Ricorda di testare a fondo il codice con vari casi di test, inclusi casi limite come alberi vuoti e alberi con tutti i valori negativi.
Modello: gemini-1.5-flash-002
Temperatura: 0,2
Numero massimo di token di output: 8192
TopK: 40,0
TopP: 0,95