BST最小节点差值方法返回异常问题排查求助

问题描述 #

我实现了用于获取二叉搜索树（BST）中任意两个不同节点最小绝对差值的getMinimumDifference()方法，但无法返回正确结果，又没法调试和使用测试工具，找不到问题所在。

需求说明 #

实现getMinimumDifference()方法，接收BST的根节点作为参数，返回树中任意两个不同节点的最小绝对差值。
假设条件：

• BST节点值大于等于0
• 所有节点值唯一
• 传入的树节点数不少于2个

示例 #

树结构：[4,2,6,1,3]
对应的树：

4
      2____||____6
 1___||___3

预期输出：1

原实现代码 #

public static int getMinimumDifference(BTNode<Integer, Integer> root) {     
        int minHolder = 9;
        BTNode<Integer, Integer> newNode = null;
        recgmd(minHolder, root, newNode);
        return minHolder;
    }
    public static void recgmd(int minHolder,BTNode<Integer, Integer> currentNode, BTNode<Integer, Integer> prevNode) {
        if(currentNode == null) {
            return;
        }
        recgmd(minHolder, currentNode.getLeftChild(), prevNode);
        if(prevNode != null){
            if(currentNode.getValue() - prevNode.getValue() <= minHolder) {
                minHolder = currentNode.getValue() - prevNode.getValue();
            }
        }
        prevNode = currentNode;
        recgmd(minHolder, currentNode.getRightChild(), prevNode);
    }

原逻辑说明 #

采用中序遍历（in-order），因为中序遍历BST会得到升序序列，便于比较当前节点与前序节点的差值。

• getMinimumDifference方法：
  • 创建minHolder变量存储最小差值
  • 创建newNode作为prevNode传入辅助方法
  • 调用辅助方法recgmd
• recgmd辅助方法：
  • 若currentNode为空则返回
  • 递归遍历左子节点
  • 若prevNode不为空，计算当前节点与前序节点的差值，若小于等于minHolder则更新
  • 更新prevNode为当前节点
  • 递归遍历右子节点

问题分析 #

原代码的核心问题在于Java的值传递特性，以及初始值设置不合理：

1. minHolder是基本类型，无法被递归方法修改：Java中int是值传递，递归方法里修改的是minHolder的副本，原方法中的变量不会有任何变化。
2. prevNode无法跨递归调用保留状态：同样因为值传递，每次递归传入的prevNode都是副本，prevNode = currentNode的赋值只在当前方法生效，下一层递归拿不到更新后的节点。
3. 初始minHolder设为9不合理：如果树中所有节点的差值都大于9，返回结果会错误，应该设为极大值（如Integer.MAX_VALUE）。

修复后的代码 #

用数组包装需要跨递归修改的变量（数组是引用类型，修改数组元素会影响原数组），同时修正初始值：

public static int getMinimumDifference(BTNode<Integer, Integer> root) {
    // 用数组包装minHolder，实现引用传递
    int[] minHolder = {Integer.MAX_VALUE};
    // 用数组包装prevNode，跨递归保留节点引用
    BTNode<Integer, Integer>[] prevNode = new BTNode[1];
    recgmd(minHolder, root, prevNode);
    return minHolder[0];
}

public static void recgmd(int[] minHolder, BTNode<Integer, Integer> currentNode, BTNode<Integer, Integer>[] prevNode) {
    if (currentNode == null) {
        return;
    }
    // 递归遍历左子树
    recgmd(minHolder, currentNode.getLeftChild(), prevNode);
    
    // 比较当前节点与前序节点的差值
    if (prevNode[0] != null) {
        int diff = currentNode.getValue() - prevNode[0].getValue();
        if (diff < minHolder[0]) {
            minHolder[0] = diff;
        }
    }
    
    // 更新前序节点为当前节点
    prevNode[0] = currentNode;
    
    // 递归遍历右子树
    recgmd(minHolder, currentNode.getRightChild(), prevNode);
}

修复点说明 #

• 用int[] minHolder替代单个int变量，确保递归中修改的是同一个值的引用
• 用BTNode[] prevNode替代单个节点变量，实现跨递归调用的状态保留
• 初始minHolder设为Integer.MAX_VALUE，保证所有可能的差值都能被正确比较
• 因为节点值唯一，用<代替<=更严谨，避免不必要的赋值

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