Python объем переменной вложенной функции: словарь vs целое число? (Решение Leetcode 662 DFS)

Question

Я смотрю на DFS-решение Leetcode 662 (https://leetcode.com/articles/maximum-width-of-binary-tree/) и запутался в области видимости переменных во вложенных функциях. Переменная max_width должна быть декалирована нелокальной, но словарь first_col_index_table этого не делает, и его можно напрямую использовать во вложенной функции. Может ли кто-нибудь помочь мне с этой проблемой переменной области? Очень ценю!

class Solution:
    def widthOfBinaryTree(self, root: TreeNode) -> int:

        # table contains the first col_index for each level
        first_col_index_table = {}
        max_width = 0

        def DFS(node, depth, col_index):
            nonlocal max_width
            if node is None:
                return
            # if the entry is empty, set the value
            if depth not in first_col_index_table:
                first_col_index_table[depth] = col_index

            max_width = max(max_width, col_index - first_col_index_table[depth] + 1)

            # Preorder DFS, with the priority on the left child
            DFS(node.left, depth+1, 2*col_index)
            DFS(node.right, depth+1, 2*col_index + 1)

        DFS(root, 0, 0)

        return max_width

Answer 1

нелокальный :

nonlocal_stmt ::=  "nonlocal" identifier ("," identifier)*

Нелокальный оператор заставляет перечисленные идентификаторы ссылаться на ранее связанные переменные в ближайшей охватывающей области, за исключением глобальных. Это важно, поскольку по умолчанию привязка выполняется сначала в локальном пространстве имен. Этот оператор позволяет инкапсулированному коду повторно связывать переменные за пределами локальной области, помимо глобальной (модульной) области. охватывающая область (область, в которой должна быть создана новая привязка, не может быть определена однозначно).

Имена, перечисленные в нелокальном операторе, не должны конфликтовать с ранее существовавшими привязками в локальной области.

Вы также можете решить проблему итеративно. Это будет проходить через:

class Solution:
    def widthOfBinaryTree(self, root):
        queue = [(root, 0, 0)]
        curr_depth = 0 
        left = 0 
        max_width = 0
        for node, depth, pos in queue:
            if node:
                queue.append((node.left, depth + 1, pos * 2))
                queue.append((node.right, depth + 1, pos * 2 + 1))
                
                if curr_depth != depth:
                    curr_depth = depth
                    left = pos
                max_width = max(max_width, pos - left + 1)
        return max_width

Или используйте self:

class Solution:
    def widthOfBinaryTree(self, root):

        # table contains the first col_index for each level
        first_col_index_table = {}
        self.max_width = 0

        def DFS(node, depth, col_index):
            if node is None:
                return
            # if the entry is empty, set the value
            if depth not in first_col_index_table:
                first_col_index_table[depth] = col_index

            self.max_width = max(self.max_width, col_index - first_col_index_table[depth] + 1)

            # Preorder DFS, with the priority on the left child
            DFS(node.left, depth+1, 2*col_index)
            DFS(node.right, depth+1, 2*col_index + 1)

        DFS(root, 0, 0)

        return self.max_width

Ссылки

• Дополнительные сведения см. На Доске обсуждения . Существует множество принятых решений с множеством языков и объяснений, эффективных алгоритмов, а также асимптот c время / пространство анализ сложности ^{1 , 2} там.