查找BST第k大节点时使用类跟踪计数相比递归传参的优势

问题1：是否必须创建TreeInfo类？能否直接递减k跟踪访问进度？ #

完全不需要强制创建TreeInfo类，也可以通过递减k的方式实现逻辑。

原实现用TreeInfo类的核心原因是Python中整数属于不可变类型，如果直接把整数k作为参数传递给递归函数，函数内部对k的修改只会作用于当前函数栈的局部变量，无法同步到外层或其他递归栈的调用，因此需要用可变对象来共享递归过程中的状态。

你可以直接通过递减k的方式实现，两种常用的无TreeInfo方案如下：

1. 用nonlocal关键字声明外层变量，在嵌套递归函数中直接修改外层状态
2. 用单元素列表这类可变容器存储k值，利用容器的可变性同步状态

以下是nonlocal实现的示例代码：

def findKthLargestValueInBst(tree, k):
    res = None
    
    def reverse_in_order(node):
        nonlocal k, res
        if not node or k <= 0:
            return
        # 逆中序遍历先访问右子树
        reverse_in_order(node.right)
        k -= 1
        if k == 0:
            res = node.value
            return
        # 最后访问左子树
        reverse_in_order(node.left)
    
    reverse_in_order(tree)
    return res

问题2：TreeInfo属于全局类/变量的说法是否正确？创建它的原因是不是用全局变量更方便？ #

这个说法完全错误。

TreeInfo是你在全局作用域定义的类，但实际用于存储状态的TreeInfo实例是在findKthLargestValueInBst函数内部初始化的，属于纯粹的函数局部变量，和全局变量没有任何关系。

创建该类的核心原因恰恰是为了避免使用全局变量：如果用全局变量存储访问计数和节点值，多次调用该函数时会出现变量污染，并发调用也会有线程安全问题。而用函数内创建的TreeInfo可变实例，既可以在不同递归栈之间共享状态，又保证了每次函数调用的状态完全独立、不会互相干扰，本质和上面示例中用nonlocal修改外层函数变量的作用完全一致。

内容的提问来源于stack exchange，提问作者Patrick_Chong