主页 / coding / 问题 / 79298842
Accepted
JobHunter69
Asked: 2024-12-21 11:55:35 +0800 CST

Leetcode 1372：为什么这两个代码片段会给出不同的结果？

  • 772

我正在解决 leetcode 问题 1372。为什么这两个代码返回不同的结果？第一个给出了正确答案。第二个没有。

# 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')

唯一的变化是这一行：

“self.longest_path = max(self.longest_path，1 + self.helper(root.left，d='l'))”

algorithm

2 个回答

  1. Best Answer

    造成差异的原因是以下两个表达式的执行顺序：

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

    helper可以为 分配一个新值，因此在调用之前还是之后self.longest_path读取都很重要——评估的顺序很重要。self.longest_path self.helper

    当避免分配给时l_path，您仍然可以通过交换传递给的参数来获得正确的执行顺序max。

    这将给出正确的结果：

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

  2. 缺少第二个代码l_path = 1 + self.helper(root.left, d='l')。

    您还可以简化代码：

    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

相关问题