为什么函数参数没有在递归 python 函数中更新？

Question

我试图在二叉搜索树中找到节点的中序后继。我的代码基本上是通过使用计数器变量进行中序遍历并跟踪下一个节点：

class Solution:
    # returns the inorder successor of the Node x in BST (rooted at 'root')
    ans = None 
    def inorderSuccessor(self, root, x):
        counter = 0
        answer = self.findNode(root, x, counter)
        return self.ans
     
    def findNode(self, root, x, counter):
        if root == None:
            return None
        self.findNode(root.left, x, counter)
        if counter == 1:
            counter += 1
            self.ans = root
            return root
        if root.data == x.data:
            ###counter becomes 1 here, when it finds the x node.
            counter += 1
        ###but it is not updated in the params.    
        self.findNode(root.right, x, counter)

这不起作用，因为递归调用永远不会更新计数器变量。

但是如果我将 counter 设为全局变量，它就可以工作了：

class Solution:
    # returns the inorder successor of the Node x in BST (rooted at 'root')
    ans = None 
    counter = 0
    def inorderSuccessor(self, root, x):
        # Code here
        answer = self.findNode(root, x)
        return self.ans
     
    def findNode(self, root, x):
        if root == None:
            return None
        self.findNode(root.left, x)
        if self.counter == 1:
            self.counter += 1
            self.ans = root
            return root
        if root.data == x.data:
            self.counter += 1
        self.findNode(root.right, x)

谁能解释一下 Python 的属性？为什么它在进行递归调用时不更新函数参数？

Answer 1

当您调用 findNode(root, x, counter) 时，如果 findNode 分配一个新值给 counter，这是对变量的赋值局部于 findNode -- 参数变量。这样的赋值不是给在函数调用中命名的这个 counter 变量。

算法的更多信息：没有必要有这样一个 counter 变量。您可以改为使用以下算法：

按照二叉搜索树的逻辑，沿着树往下走。当 x.data 小于当前节点的数据时，向左走，否则向右走。每次你向左走，记下你来自哪里，因为它可能就是我们正在寻找的继任者。

一旦到达树中这条向下路径的末端，回想一下哪个节点是决定向左走的最后一个节点。那就是继任者。

代码：

    def inorderSuccessor(self, root, x):
        candidate = None
        while root:
            if x.data < root.data:
                candidate = root
                root = root.left
            else:
                root = root.right
        return candidate

为什么函数参数没有在递归 python 函数中更新？

Why are the function parameters not being updated inside recursive python function?

python

algorithm

depth-first-search