Проверка, является ли дерево двоичного поиска вырожденным

Question

Я хочу проверить, вырождено ли дерево двоичного поиска или нет (это связанный список или действительно дерево?) Я пытался какое-то время и придумал ничто не работает. Я придумал нерекурсивное решение, которое, как я думал, было довольно умным, но спецификации указывают, что оно должно быть рекурсивным решением, и я переводил его из нерекурсивного в рекурсивный.

Вот мое нерекурсивное решение (ну не совсем потому, что размер и высота реализованы рекурсивно. Однако этот метод не является).

public boolean isDegenerate(){ 
     if(this.size() == this.getHeight()){ 
      return true; 
     } 
     return false; 
    } 

Answer 1

Ну, если вы хотите «более рекурсивное» решение, как насчет этого?

public boolean isDegenerate() { 
    if (this.left != null) { 
     if (this.right != null) { 
      return false; // not degenerate, has two children 
     } else { 
      return this.left.isDegenerate(); 
     } 
    } else { 
     if (this.right != null) { 
      return this.right.isDegenerate(); 
     } else { 
      return true; // we arrived at the bottom without seeing any node with two children 
     } 
    } 
}