Java递归验证二叉搜索树代码空指针异常问题求助

问题描述 #

尝试实现递归线性时间算法验证BST节点规范，代码运行时抛出NullPointerException，提示n为null，但确认树已填充且节点存在。相关代码如下：

BinaryTree类代码 #

public class BinaryTree {
    Node root;

    private Node addR(Node c, int x, Node parent) {
        if (c == null) {
            c = new Node(x);
            c.parent = parent;
            return c;
        }
        if (x < c.value) {
            parent = c;
            c.left = addR(c.left, x, c);
        }
        else if (x > c.value) {
            parent = c;
            c.right = addR(c.right, x, c);
        }
        else {
            return c;
        }
        return c;
    }
    
    public void add(Node parent, int x) {
        root = addR(root, x, parent);
    }
    
    static int max(Node n) {
        if (n == null) {
            return Integer.MIN_VALUE;
        }
        int value = n.value;
        int leftMax = max(n.left);
        int rightMax = max(n.right);
        return Math.max(value, Math.max(leftMax, rightMax));
    }
        
    static int min(Node n) {
        if (n == null) {
            return Integer.MAX_VALUE;
        }
        int value = n.value;
        int leftMax = min(n.left);
        int rightMax = min(n.right);
        
        return Math.min(value,  Math.min(leftMax, rightMax));
    }
    
    static int verifyBST(Node n) {
        if (n.left != null && max(n.left) > n.value) {
            return 0;
        }
        
        if (n.right != null && min(n.right) < n.value) {
            return 0;
        }
        if (verifyBST(n.left) != 1 || verifyBST(n.right) != 1) {
             return 0;
        }
        return 1;
     }
    
    static void verifyBSTout(int x) {
        if (x == 1) {
            System.out.println ("Confirmed Binary Tree.");
        }
        else {
            System.out.println ("Not a Binary Tree.");
        }
    }
}

Main类代码 #

public class Main {
    public static void main(String[] args) {
        BinaryTree test = new BinaryTree();
        test.add(test.root, 7);
        test.add(test.root, 5);
        test.add(test.root, 6);
        test.add(test.root, 9);
        test.add(test.root, 3);
        test.add(test.root, 8);
        test.verifyBSTout(BinaryTree.verifyBST(test.root));
        
    }
}

错误原因分析 #

verifyBST方法未处理输入节点n为null的边界情况：

• 递归到叶子节点时，其left或right为null，此时调用verifyBST(null)；
• 进入方法后直接执行n.left != null的判断，但n本身是null，访问n.left会立即抛出NullPointerException。

另外，当前实现的时间复杂度并非线性：每次调用max/min都会遍历整个子树，导致整体时间复杂度为O(n²)，不符合你想要的线性时间要求。

修复方案 #

1. 先处理空节点的边界情况 #

修改verifyBST方法，优先判断节点是否为null，直接返回1（空树是合法BST）：

static int verifyBST(Node n) {
    // 空节点直接返回合法
    if (n == null) {
        return 1;
    }
    
    if (n.left != null && max(n.left) > n.value) {
        return 0;
    }
    
    if (n.right != null && min(n.right) < n.value) {
        return 0;
    }
    
    return verifyBST(n.left) == 1 && verifyBST(n.right) == 1 ? 1 : 0;
}

2. 优化为线性时间算法 #

通过传递当前节点的取值上下界，一次递归遍历完成验证，时间复杂度O(n)：

// 对外暴露的验证方法
static int verifyBST(Node n) {
    return verifyBSTHelper(n, Integer.MIN_VALUE, Integer.MAX_VALUE);
}

// 递归辅助方法，传递上下界
private static int verifyBSTHelper(Node n, int lowerBound, int upperBound) {
    if (n == null) {
        return 1;
    }
    // 当前节点值超出上下界，不合法
    if (n.value <= lowerBound || n.value >= upperBound) {
        return 0;
    }
    // 左子树的上界是当前节点值，右子树的下界是当前节点值
    return verifyBSTHelper(n.left, lowerBound, n.value) == 1 
        && verifyBSTHelper(n.right, n.value, upperBound) == 1 ? 1 : 0;
}

这种方式避免了重复调用max/min遍历子树，真正实现线性时间复杂度，同时也自然处理了空节点的情况。

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