BST 中第 K 个最小元素的静态和非静态差异

Question

在这个问题中，如果我在第二行 static 中创建 count 变量，如图所示，kthSmallest() 方法计算出错误的答案。如果变量改为非 static，则计算出正确答案。非静态方法可以使用静态变量，为什么会有区别？

class Solution {
    public static int count = 0;
    public int res = 0;

    public int kthSmallest(TreeNode root, int k) {
        inorder(root,k);
        return res;
    }

    public void inorder(TreeNode root, int k) {
        if (root == null) return;
        inorder(root.left,k);
        count++;
        if (count == k) {
            res = root.val;
            return;
        }
        inorder(root.right,k);
    }
}

Answer 1

我看不出为什么您的 kthSmallest() 方法的单个运行 的结果会受到 count 是否 static，但是如果执行多个运行，不管是顺序还是并行，肯定会有问题。 count 是 static 意味着 class Solution 的每个实例共享该变量，您将其初始化一次为零，然后仅递增。该方法的第二个运行，无论是在 Solution 的相同实例还是不同实例上，都将继续使用前一个运行.[=25 留下的 count 的值=]

通过确保 Solution 的每个实例都有自己的 count 变量，使 count 非 static 部分解决了该问题。使用同一实例执行多个 kthSmallest() 计算仍然存在问题，但您可以对每个实例执行一个正确的运行。如果您通过一些自动判断来测试它，那么它确实确实为每个测试用例创建了一个单独的实例是合理的。

但即使这样也不是完整的解决方案。每个实例您仍然最多获得一个运行，如果尝试使用同一实例执行两个并发运行，您甚至不确定是否获得它。这里的根本问题是您正在使用实例（或 class）变量来保存特定于 kthSmallest() 方法的单个运行的状态。

您应该改为使用该方法的局部变量，如果需要，通过方法参数和/或 return 值与其他方法通信。例如：

class Solution {
    // no class or instance variables at all

    public int kthSmallest(TreeNode root, int k) {
        // int[1] is the simplest mutable container for an int
        int[] result = new int[1];
        inorder(root, k, result);
        return result[0]; 
    }

    // does not need to be public:
    // returns the number of nodes traversed (not necessarily the whole subtree)
    int inorder(TreeNode root, int k, int[] result) {
        if (root == null) {
            return 0;
        } else {
            // nodes traversed in the subtree, plus one for the present node
            int count = inorder(root.left, k, result) + 1;

            if (count == k) {
                result[0] = root.val;
            } else {
                count += inorder(root.right, k, result);
            }

            return count;
        }
    }
}

BST 中第 K 个最小元素的静态和非静态差异

static and non-static difference in Kth Smallest Element in a BST

java

static

non-static