使用包装器 class 而不是静态变量

Question

这是我在 Whosebug 上的第一个问题：我在"Cracking the code interview"（第5版）书的帮助下学习面试，我正在解决下一个问题：

Implement a function to check if a binary tree is a binary search tree (Q 4.5 pg 86).

在我们继续之前，我想提醒您二叉搜索树与简单二叉树之间的区别：

A Binary search tree imposes the condition that for all nodes, the left children are less than or equal to the current node, which is less than all the right nodes.

所以这本书提供的解决方案之一是用中序遍历扫描树，并在运行中检查我们访问的每个节点是否都大于最后一个节点，它假设树不能有重复值：

public static int last_printed = Integer.MIN_VALUE;
public static boolean checkBST(TreeNode n) {
    if(n == null) return true;

        // Check / recurse left
        if (!checkBST(n.left)) return false;

        // Check current
        if (n.data <= last_printed) return false;
        last_printed = n.data;

        // Check / recurse right
        if (!checkBST(n.right)) return false;

        return true; // All good!
}

现在，这里一切都很好，但是书上引用了：

If you don't like the use of static variables, then you can tweak this code to use a wrapper class for the integer, as shown below:

Class WrapInt {
    public int value;
}

在阅读了此处和其他网站上的包装器 class 之后，我无法得出结论，为什么以及如何在这里使用包装器 class 而不是静态变量？

Answer 1

这是一种机制，您可以通过该机制创建 WrapInt 的实例，并将其四处传递。然后，您仅将该值公开给应该知道它的代码，而不是可以从任何地方访问和更改的 public 静态非最终变量。

您拥有包装器 class 的原因是因为 Java 原语是按值传递的；传递一个 int 然后更新它不会将更改传播到系统的其余部分。

这看起来像这样：

public static boolean checkBST(TreeNode n) {
    WrapInt counter = new WrapInt();
    return checkBST(n, counter);
}

public static boolean checkBST(TreeNode n, WrapInt counter) {
    if(n == null) return true;

        // Check / recurse left
        if (!checkBST(n.left, counter)) return false;

        // Check current
        if (n.data <= counter.value) return false;
        counter.value = n.data;

        // Check / recurse right
        if (!checkBST(n.right, counter)) return false;

        return true; // All good!
}

Answer 2

给你：

public static boolean checkBST(TreeNode n) {
     WrapInt i = new WrapInt();
     i.value = INTEGER.MIN_VALUE;
     doCheckBST(n, i);
}

private static boolean doCheckBST(TreeNode n, WrapInt last_printed) {
if(n == null) return true;

    // Check / recurse left
    if (!checkBST(n.left, last_printed)) return false;

    // Check current
    if (n.data <= last_printed.value) return false;
    last_printed.value = n.data;

    // Check / recurse right
    if (!checkBST(n.right, last_printed)) return false;

    return true; // All good!
}

Answer 3

如果有可能运行 2+次同时排序。静态将用于两种排序。两种排序都可以访问相同的静态值。

//thread 1
Sorting A = new Sorting(5,9,8);
A.sort();

//thread 2
Sorting B = new Sorting(999,100,7);
B.sort();

我们无法预测 which/how 线程已处理。

所以这可能会在

A.checkBST(5)    // last_printed  = 5
B.checkBST(999)  // last_printed  = ??
B.checkBST(100)  // last_printed  = ??
A.checkBST(9)    // last_printed  = ??

... ...

如果每个排序实例都有自己的 last_printed，您就不会有同步问题。

Answer 4

静态变量的问题是另一个 class/method 或其他东西可以修改它，它会破坏你的代码。可以这样吗:

Class WrapInt {
public int value=Integer.MIN_VALUE;
} 

public static boolean checkBST(TreeNode n,WrapInt lastPrinted) {
if(n == null) return true;

    // Check / recurse left
    if (!checkBST(n.left,lastPrinted)) return false;

    // Check current
    if (n.data <= lastPrinted.value) return false;
    lastPrinted.value = n.data;

    // Check / recurse right
    if (!checkBST(n.right,lastPrinted)) return false;

    return true; // All good!

}

Answer 5

我认为这是如何避免 public 静态上下文属性（例如线程安全）的更正式的方法，这不是对象编程中的最佳方法。但是有标准的 Primitive wrapper 类作为：https://docs.oracle.com/javase/7/docs/api/java/lang/Integer.html 可以用来代替 new 类。通常 Wrapper 模式可以比您的示例更通用：What is a wrapper class?

使用包装器 class 而不是静态变量

Using wrapper class instead of static variables

java

static

binary-tree

binary-search-tree

wrapper