11.19实验：二叉搜索树（BST）有效性检查器代码验证问询

实验背景与要求 #

本次为11.19的二叉搜索树（BST）有效性检查实验，核心要求如下：

• 基于包含key、左/右子节点引用的Node.java实现BSTChecker类；
• 实现checkBSTValidity()方法：接收树根节点，返回首个违反规则的节点（无违规则返回null）；
• 需要检测三类违规节点：
  1. 位于键值更小的祖先节点的左子树中；
  2. 位于键值更大的祖先节点的右子树中；
  3. 子节点引用指向祖先节点（树存在环）。

实验配套的LabProgram.java会通过(key, leftChild, rightChild)格式的输入构建树，最终输出违规节点的key或"No violation"。

你的实现代码 #

import java.util.*;

public class BSTChecker {
    public static Node checkBSTValidity(Node rootNode) {
        return checkBSTValidity(rootNode, null, null);
    }
    
    private static Node checkBSTValidity(Node node, Node min, Node max) {
        if (node == null) {
            return null;
        }
    
        // 检查当前节点是否违反BST规则
        if ((min != null && node.key <= min.key) || (max != null && node.key >= max.key)) {
            return node;
        }
    
        // 检查左右子树
        Node leftViolation = checkBSTValidity(node.left, min, node);
        Node rightViolation = checkBSTValidity(node.right, node, max);
    
        // 返回找到的违规节点
        if (leftViolation != null)
            return leftViolation;
        else if (rightViolation != null)
            return rightViolation;
        else
            return null;
    }
}

代码验证结论 #

你的代码能正确检测前两类值规则违规情况，但完全无法处理第三类环违规（子节点指向祖先）：

• 当前递归逻辑没有记录已访问节点，若树存在环（如某个子节点直接/间接指向祖先），递归会无限循环，最终抛出StackOverflowError，无法返回违规节点。

修复方案（覆盖所有三类违规） #

添加Set<Node>跟踪已访问节点，修改后的代码如下：

import java.util.*;

public class BSTChecker {
    public static Node checkBSTValidity(Node rootNode) {
        return checkBSTValidity(rootNode, null, null, new HashSet<>());
    }
    
    private static Node checkBSTValidity(Node node, Node min, Node max, Set<Node> visited) {
        if (node == null) {
            return null;
        }
    
        // 检测环：当前节点已被访问，说明存在子节点指向祖先的违规
        if (visited.contains(node)) {
            return node;
        }
        visited.add(node);
    
        // 检测值规则违规
        if ((min != null && node.key <= min.key) || (max != null && node.key >= max.key)) {
            return node;
        }
    
        // 检查左子树
        Node leftViolation = checkBSTValidity(node.left, min, node, visited);
        if (leftViolation != null) {
            return leftViolation;
        }
    
        // 检查右子树
        Node rightViolation = checkBSTValidity(node.right, node, max, visited);
        if (rightViolation != null) {
            return rightViolation;
        }
    
        // 回溯：移除当前节点，不影响其他分支遍历
        visited.remove(node);
        return null;
    }
}

修复说明 #

1. 新增Set<Node> visited参数，记录遍历过的节点，用于检测环；
2. 进入节点时先检查是否已访问，若已访问则直接返回该节点（判定为环违规）；
3. 遍历完当前节点的子树后，从visited中移除节点（回溯处理，保证其他分支的正确性）；
4. 保留原有的值范围检查逻辑，确保前两类违规能被检测。

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