Python 的 nonlocal 关键字 - 这是好的做法吗？

Question

考虑一个简单的情况，例如在 BST 中查找第 k 个最小元素。

在我下面的解决方案中：

class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        i = 0
        ans = -1
        def traverse_inorder(root):
            nonlocal i
            nonlocal ans
            if not root:
                return
            traverse_inorder(root.left)
            i += 1
            if i == k:
                ans = root.val
                return
            traverse_inorder(root.right)
        traverse_inorder(root)
        return ans

我使用nonlocalfori和是ans好的做法吗？我这样做是为了跟踪到达最左边的节点（最小值）后我遍历了多少个元素。

另一个解决方案是将i和ans作为类的成员变量：

class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        self.i = 0
        self.ans = -1
        def traverse_inorder(root):
            # etc etc

两种方法等效吗？一种练习是否比另一种更好，为什么？

Answer 1

我认为在你描述的情况下，这种nonlocal方法客观上比你展示的另一种方法更有意义。您的目标是在函数之外有一个计数器，以及一种在找到结果时跟踪结果的方法，无论您处于递归中的哪个位置。

nonlocal将该信息完全封装在专用于外部函数的特定运行的命名空间中。这里确实没有什么缺点。

使用实例属性使使用该实例的任何人都可以使用该信息。这在概念上是不必要的，速度稍慢，而且不是线程安全的。虽然线程安全在 Python 中通常不是一个问题，但它确实会降低您的代码的健壮性。在这和封装之间，我肯定会远离这种方法。

我在这里建议第三种可能性：使用返回值。在这种情况下，您确实不需要任何外部名称空间。我不一定推荐这样做而不是使用nonlocal，但值得一提。这是一个示例实现，正如您所看到的，它比您的解决方案要详细得多：

class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        def traverse_inorder(root, target):
            if not root:
                return 0, None
            left_count, item = traverse_inorder(root.left, target)
            if left_count == target - 1:
                 return left_count + 1, root.val
            elif left_count < target:
                 right_count, item = traverse_inorder(root.right, target - left_count - 1)
                 return left_count + right_count + 1, item
            else:  # left_count == target
                 return left_count, item
        count, ans = traverse_inorder(root, k)
        if count < k:
            raise ValueError('Insufficient elements')
        return ans

有很多方法可以通过返回值来做到这一点。在这里，我计算每个子树中的元素数量，直到目标值。仅当找到确切数量的元素时才返回非空项。