Java实现BST第k小元素时如何在void递归中修改外部变量

问题根因 #

Java只有值传递，且Integer是不可变类：你向traverse函数传入的cnt、ans本质是原引用的拷贝，在函数内部直接给ans重新赋值ans = new Integer(root.val)，只是修改了局部拷贝的指向，完全不会影响外部的原变量，这就是你始终返回0的核心原因。

以下两种方案都不需要修改traverse的void返回类型，即可实现内部修改外部值的需求： #

方案1：使用数组作为可变容器（代码改动最小） #

用长度为1的int数组存储cnt和ans，数组是可变对象，修改数组元素会同步到外部的原数组：

class Solution {
    public int kthSmallest(TreeNode root, int k) {
        int[] cnt = new int[]{1};
        int[] ans = new int[]{0};
        traverse(root, k , cnt, ans);
        return ans[0];
    }
    
    void traverse(TreeNode root, int k, int[] cnt, int[] ans){
        if(root == null) return;
        
        traverse(root.left, k, cnt, ans);
        if(cnt[0]++ == k){
            ans[0] = root.val;
            return;
        }
        traverse(root.right, k, cnt, ans);
    }
}

方案2：使用类的成员变量 #

把cnt和ans定义为Solution类的实例属性，递归函数可以直接修改属性值，不需要作为参数传递：

class Solution {
    int cnt;
    int ans;
    public int kthSmallest(TreeNode root, int k) {
        cnt = 1;
        ans = 0;
        traverse(root, k);
        return ans;
    }
    
    void traverse(TreeNode root, int k){
        if(root == null) return;
        
        traverse(root.left, k);
        if(cnt++ == k){
            ans = root.val;
            return;
        }
        traverse(root.right, k);
    }
}

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