Início / coding / Perguntas / 79298842
Accepted
JobHunter69
Asked: 2024-12-21 11:55:35 +0800 CST

Leetcode 1372: Por que esses dois trechos de código dão resultados diferentes?

  • 772

Estou resolvendo um problema leetcode 1372. Por que esses dois códigos retornam resultados diferentes? O primeiro dá a resposta correta. O segundo não.

# Definition for a binary tree node.

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

    def longestZigZag(self, root: Optional[TreeNode]) -> int:
        val1 = 1 + self.helper(root.right, 'r')
        val2 = 1 + self.helper(root.left, 'l')
        # print(val2, self.longest_path)
        val = max(val1, val2)
        return max(val, self.longest_path) - 1

    def helper(self, root, d):
        if root == None:
            return 0
        if d == 'l':
            l_path = 1 + self.helper(root.left, d='l')
            self.longest_path = max(self.longest_path, l_path)
            return 1 + self.helper(root.right, d='r')
        if d == 'r':
            r_path = 1 + self.helper(root.right, d='r')
            self.longest_path = max(self.longest_path, r_path)
            return 1 + self.helper(root.left, d='l')
        



class Solution:
    def __init__(self):
        self.longest_path = 0

    def longestZigZag(self, root: Optional[TreeNode]) -> int:
        val1 = 1 + self.helper(root.right, 'r')
        val2 = 1 + self.helper(root.left, 'l')
        # print(val2, self.longest_path)
        val = max(val1, val2)
        return max(val, self.longest_path) - 1

    def helper(self, root, d):
        if root == None:
            return 0
        if d == 'l':
            self.longest_path = max(self.longest_path, 1 + self.helper(root.left, d='l'))
            return 1 + self.helper(root.right, d='r')
        if d == 'r':
            r_path = 1 + self.helper(root.right, d='r')
            self.longest_path = max(self.longest_path, r_path)
            return 1 + self.helper(root.left, d='l')

A única mudança é esta linha:

"self.longest_path = max(self.longest_path, 1 + self.helper(root.left, d='l'))"

algorithm

2 respostas

  1. Best Answer

    O motivo da diferença é a ordem de execução das duas expressões a seguir:

    1. 1 + self.helper(root.left, d='l')
    2. self.longest_path

    helperpode atribuir um novo valor a self.longest_path, então importa se você lê self.longest_path antes ou depois da chamada de self.helper-- a ordem de avaliação é importante.

    Ao evitar a atribuição para l_path, você ainda pode obter a ordem correta de execução trocando os argumentos passados ​​para max.

    Isso dará o resultado correto:

    self.longest_path = max(1 + self.helper(root.left, d='l'), self.longest_path)
#                       ---------------------------- swapped ---------------
    • 1

  2. O segundo código está faltando l_path = 1 + self.helper(root.left, d='l').

    Você também pode simplificar o código:

    class Solution:
    def longestZigZag(self, root):
        def dfs(node):
            if not node:
                return [-1, -1, -1]
            l = dfs(node.left)
            r = dfs(node.right)
            return [l[1] + 1, r[0] + 1, max(l[1] + 1, r[0] + 1, l[2], r[2])]

        return dfs(root)[-1]
    • -1

relate perguntas