Рекурсивно найти минимальное значение в двоичном дереве в Java

Question

Мне нужно найти минимальное значение в дереве строк, которое не является двоичным деревом поиска рекурсивно. Я попытался рассмотреть некоторые другие вопросы, подобные моим, но я не мог понять ответ.

Я выяснил, что мне нужно найти мин каждого из поддеревьев, затем сравнить его с корнем и вернуть минимальное значение. Но я не уверен, как это написать.

Это заголовок:

public static Object min(TreeNode t){ 

} 

EDIT: Так что я понял, до сих пор это

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; 
    } 
} 

Я думаю, что я иду в правильном направлении, но я «Не знаю, что подходит в заявлении return в нулевом базовом случае. Может ли кто-нибудь помочь мне понять, что должно быть в возвращении и почему? И если я сделаю это правильно? Спасибо

Answer 1

Вам необходимо обработать getLeft или getRight, также являясь нулевым, иначе ваш код заканчивается исключениями.

Тогда ваш случай для любого большего, чем сравнение, не следует вводить, если вы хотите «минимум», я не думаю.

Кто сказал, что вы не можете вернуть null?

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; 
}