递归查找 Java 中二叉树中的最小值

Question

>我需要在不是二叉搜索树的字符串树中以递归方式找到最小值。我试着看一些像我这样的问题，但我无法找出答案。

我已经发现我必须找到每个子树的最小值，然后将其与根进行比较，并返回最小值。但我不确定如何实际写它。

这是标头：

public static Object min(TreeNode t){
}

编辑：所以到目前为止我发现的是这个

public static Object min(TreeNode t){
    if(t == null){
        return ______;
    }
    else if(min(t.getLeft().compareTo(min(t.getRight()) < 0){
        if(min(t.getLeft()).compareTo(t) < 0){
            return min(t.getLeft());
        }
    }
    else if(min(t.getLeft().compareTo(min(t.getRight()) > 0){
        if(min(t.getRight()).compareTo(t) < 0){
            return min(t.geRight());
        }
    }
    else{
        return t;
    }
}

我认为我正朝着正确的方向前进，但我不确定在空基本情况下什么适合返回语句。有人可以帮助我了解返回声明中应该包含什么以及为什么？如果我这样做是对的呢？谢谢

Answer 1

你需要

处理getLeft或getRight也是空的，否则你的代码最终会出现异常。

然后，如果您想要"最小值"，则不应输入任何大于比较的情况，我认为。

谁说你不能返回空？

public static Object min(TreeNode t){
    TreeNode min = t;
    if(t == null){
        return min;
    }
    final TreeNode left = t.getLeft();
    final TreeNode right = t.getRight();
    if (left == null && right == null) 
        return min;
    if(left != null && left.compareTo(t) <= 0) {
        min = (TreeNode) min(left);
    if(min != null && right != null && right.compareTo(t) > 0){ // not sure about this 
        min = (TreeNode) min(right);
    }
    return min;
}