Python: 嵌套函数中的引用变量指向外部作用域（非全局）

Question

我正在尝试递归遍历一棵树，并跟踪遍历的路径，直到找到我要找的元素。然而，我遇到了两个问题：

1. 虽然我的当前代码返回了正确的解决方案，但它有点hacky。我必须将正在遍历的当前路径推入final_path，然后返回final_path [0]。如果我只是尝试设置final_path = path，其中final_path在外部范围中定义，它不起作用。如何引用嵌套函数的外部范围？
2. 如果值不在树中，则最终会以预先订购的方式遍历整个树。是否有任何方法来构造代码，以便我可以说“如果在遍历结束时我们没有找到目标元素，那么只需返回[]而不是完整路径”？我意识到我可以循环遍历并检查每个元素，但这似乎非常冗余。

代码：

lftlft = {'val': 3, 'left': None, 'right': {'val': 100, 'left': None, 'right': None}}
rtrt = {'val': 5, 'left': None, 'right': None}
lft = {'val': 2, 'left': lftlft, 'right': {'val': 99, 'left': None, 'right': None}}
rt = {'val': 4, 'left': None, 'right': rtrt}
T = {'val': 1,'left': lft, 'right': rt}

def get_path(root, data, path):
    final_path = []

    def pre_order(tree, path):
        if tree is None:
            return

        path.append(tree['val'])

        if tree['val'] == data:
            final_path.append(path)
            return True

        return pre_order(tree['left'], path[:]) or pre_order(tree['right'], path[:])

    pre_order(root, [])
    print('finalpath', final_path)
    return final_path[0]

get_path(T, 99, [])

- TheRealFakeNews

Answer 1

在Python 3.x中，您只需要使用关键字nonlocal。在您的内部函数开头使用它，就像使用global一样。

def get_path(root, data, path):
    final_path = ...

    def pre_order(tree, path):
        nonlocal final_path
        ...
    ...

    return final_path

即使在Python 2.x中，只要引用变量就会自动授予您读取访问权限 - 但从不授权写入访问权限。请注意，如果所引用的对象是可变对象（例如列表或字典），则可以在内部函数中进一步修改它。

随着Python 3.0中nonlocal关键字的引入，您可以完全写入外部函数作用域中定义的变量。

在Python 2.x中，使用内部函数将数据写入外部范围列表的一个特定元素可能是解决此问题的最佳方法。

- jsbueno

Answer 2

我意识到我不必迭代来检查它是否被找到。不知道为什么我之前没有想到添加一个标志。

rtrt = {'val': 5, 'left': None, 'right': None}
lft = {'val': 2, 'left': lftlft, 'right': {'val': 99, 'left': None, 'right': None}}
rt = {'val': 4, 'left': None, 'right': rtrt}
T = {'val': 1,'left': lft, 'right': rt}


def get_path(root, data, path):
    final_path = []
    found = False

    def pre_order(tree, path):
        if tree is None:
            return

        path.append(tree['val'])

        if tree['val'] == data:
            nonlocal final_path, found
            final_path = path
            found = True
            return found

        return pre_order(tree['left'], path[:]) or pre_order(tree['right'], path[:])

    pre_order(root, [])
    if not found:
        return []

    return final_path

get_path(T, 999, [])

- TheRealFakeNews

Answer 3

我认为问题出在你从get_path调用pre-order时没有捕获返回值。

对于我来说，以下代码似乎得到了与你的示例代码相同的结果，如果我将值99更改为其他数字，则会得到None的返回值。

lftlft = {'val': 3, 'left': None, 'right': {'val': 100, 'left': None, 'right': None}}
rtrt = {'val': 5, 'left': None, 'right': None}
lft = {'val': 2, 'left': lftlft, 'right': {'val': 99, 'left': None, 'right': None}}
rt = {'val': 4, 'left': None, 'right': rtrt}
T = {'val': 1,'left': lft, 'right': rt}

def get_path(root, data, path):

    def pre_order(tree, path):
        if tree is None:
            return

        path.append(tree['val'])

        if tree['val'] == data:
            return path
        return pre_order(tree['left'], path[:]) or pre_order(tree['right'], path[:])

    desired_result = pre_order(root, [])
    return desired_result

print (get_path(T, 99, []))

- R.Sharp

Answer 4

这是一个XY问题。你可以做你要求的事情，但实际上是在给你的函数添加全局状态。而且，使用final_path已经意味着你正在使用全局状态，应该尽可能避免使用（在这种情况下是可能的）。

有几种方法可以解决你的问题。首先，你可以使用final_path.extend(path)代替final_path.append(path)。这样，不是将path作为元素添加到final_path中，而是将path的所有元素作为final_path的元素添加进去。但你仍然在使用全局状态，这并不好。

相反，您可以使用Python对象的“真实性”，以便返回不同类型。也就是说，您可以返回路径本身，而不是返回True，并且仅在返回路径时附加当前的val。如果没有找到路径，则返回类似于[]的假值。这将创建一个反转的路径，但您可以在最后反转path。例如：

def get_path(root, data, path):

    def pre_order(tree):
        if not tree:
            # base case, data not found
            return [] # counts as false
        elif tree['val'] == data:
            # base case, found data
            return [data] # counts as true
        else:
            # recursive case
            path = pre_order(tree['left']) or pre_order(tree['right'])
            if path:
                # data was found, add the current val to the path
                path.append(tree['val'])
            return path

    final_path = pre_order(root)
    final_path.reverse()
    print('finalpath', final_path)
    return final_path

最后，你想要编写解决方案的答案是使用关键字nonlocal。这允许你更改final_path指向的对象，而不仅仅是改变对象本身。例如：

def f():
    x = 1
    def g():
        nonlocal x
        x = 2
    g()
    print("x =", x) # prints x = 2

- Dunes