Java中调用isBstTree方法前HashSet出现意外值问题

原始代码 #

package main;

import java.io.*;
import java.util.*;

public class IsBSTTree {

     Set<Integer> set = new HashSet<>();

        public static void main(String[] args) throws IOException {
            BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
            PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
            String[] line = in.readLine().split(" ");
            IsBSTTree solution = new IsBSTTree();
            Node root = solution.buildTree(line, 0, line.length - 1);
            if (solution.isBstTree(root, Integer.MIN_VALUE, Integer.MAX_VALUE)) {
                out.println("Yes");
            } else {
                out.println("No");
            }
            out.flush();
        }

        Boolean isBstTree(Node node, int min, int max) {
            
            if (node == null) 
                return true;

            if (node.data <= min || node.data >= max) 
                return false;
            if (set.contains(node.data)) 
                return false;
            
            set.add(node.data);

            if (isBstTree(node.left, min, node.data) || 
                    isBstTree(node.right, node.data, max)) {
                return false;
            }

            return false;
        }

        public Node buildTree(String[] arr, int from, int to) {
            if (from > to) return null;

            int middle = from + (to - from) / 2;
            Node node = new Node();
            node.data = Integer.valueOf(arr[middle]);
            node.left = buildTree(arr, from, middle - 1);
            node.right = buildTree(arr, middle + 1, to);
            return node;
        }

        class Node {
            int data;
            Node left;
            Node right;
        }
    }

问题描述 #

• 使用成员变量set（HashSet<Integer>类型）追踪节点值，用于检测重复并验证二叉搜索树（BST）。
• 调试时发现，在调用isBstTree方法前，set中已存在值。
• 预期行为：set在isBstTree方法启动时为空，仅在方法执行过程中被填充。

实际行为 #

调用isBstTree方法前，set中已包含值。

疑问 #

1. 为何isBstTree方法调用前set中会存在值？
2. 需要进行哪些修改才能确保set符合预期行为？

解答 #

问题1：调用前set已有值的原因 #

根据你提供的代码，理论上调用isBstTree前set应该是空的——set是实例变量，创建IsBSTTree实例时会初始化空集合，而buildTree仅负责构建树，不会操作set。出现异常的可能原因：

• 旧代码残留/缓存问题：如果之前的代码版本中buildTree或其他方法有操作set的逻辑，且编译后的class文件未更新，会导致运行旧逻辑。
• 调试操作失误：调试时可能误触发了isBstTree的执行（比如提前步进代码），或断点位置错误，误以为未调用方法但实际已进入执行流程。
• 调试工具显示bug：部分工具可能错误展示了其他实例的set内容。

问题2：修改方案 #

要确保set仅在isBstTree执行时使用且初始为空，同时修复方法的逻辑错误，建议做以下修改：

核心修改点

1. 移除成员变量set，改用局部变量+参数传递：避免实例状态残留，每次调用isBstTree都会初始化新的空集合。
2. 修复递归判断逻辑：原代码用||判断左右子树，这是错误的——BST要求左右子树都必须符合规则，应改用&&；同时原方法最后固定返回false，完全不符合逻辑，需修正为返回左右子树的判断结果。

修改后的完整代码

package main;

import java.io.*;
import java.util.*;

public class IsBSTTree {

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
        String[] line = in.readLine().split(" ");
        IsBSTTree solution = new IsBSTTree();
        Node root = solution.buildTree(line, 0, line.length - 1);
        if (solution.isBstTree(root)) {
            out.println("Yes");
        } else {
            out.println("No");
        }
        out.flush();
    }

    // 对外方法，初始化空集合并调用递归辅助方法
    Boolean isBstTree(Node node) {
        return isBstTreeHelper(node, Integer.MIN_VALUE, Integer.MAX_VALUE, new HashSet<>());
    }

    // 递归辅助方法，将set作为参数传递，彻底避免状态污染
    Boolean isBstTreeHelper(Node node, int min, int max, Set<Integer> set) {
        if (node == null)
            return true;

        // 检查当前节点的合法性与唯一性
        if (node.data <= min || node.data >= max || set.contains(node.data))
            return false;
        
        set.add(node.data);

        // 左右子树都必须符合BST规则，使用&&连接
        return isBstTreeHelper(node.left, min, node.data, set) &&
               isBstTreeHelper(node.right, node.data, max, set);
    }

    public Node buildTree(String[] arr, int from, int to) {
        if (from > to) return null;

        int middle = from + (to - from) / 2;
        Node node = new Node();
        node.data = Integer.valueOf(arr[middle]);
        node.left = buildTree(arr, from, middle - 1);
        node.right = buildTree(arr, middle + 1, to);
        return node;
    }

    class Node {
        int data;
        Node left;
        Node right;
    }
}

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