StackOverflowError beim Durchlaufen einer binären Suchstruktur in Java

Question

Ich habe eine Methode, die den tiefsten Knoten in einer BST zurückgibt. Ich habe diesen Code, die einen Fehler auslöst Stackoverflow:

public int getDeepestNode(AvlNode head) { 
    if (head == null) { 
     return 0; 
    } else { 
     return (Math.max(getDeepestNode(head.getLeftNode()), getDeepestNode(head.getRightNode())) + 1); 
    } 
} 

Für mich ist es sieht gut aus, warum ist es, den Fehler verursacht?

Answer 1

getDeepestNode muss wiederholt auf dem Stapel auftreten.

Mehr als wahrscheinlich haben Sie einen Zyklus in der AVL-Struktur. Die Benennung head könnte schon ein Hinweis auf unsaubere Gedanken sein. Debugging hilft. Alternativ können Sie Ihren Code verhärten wie:

public int getDeepestNode(AvlNode head) { 
    return getDeepestNodeSafe(head, new ArrayList<AvlNode>()); 
} 

public int getDeepestNodeSafe(AvlNode head, List<AvlNode> pathFromRoot) { 
    if (head == null) { 
     return 0; 
    } else { 
     if (pathFromRoot.contains(head)) { 
      StringBuilder sb = new StringBuilder("Cycle: "); 
      for (AvlNode node : pathFromRoot) { 
       if (node == head) { 
        sb.append("***"); 
       } 
       sb.append(node).append("; "); 
      } 
      Logger.getLogger(getClass().getName()).log(Level.WARN, sb.toString()); 
      return 0; 
     } 
     pathFromRoot.add(head); 
     int depth = Math.max(getDeepestNodeSafe(head.left, pathFromRoot), 
          getDeepestNodeSafe(head.right), pathFromRoot) + 1; 
     pathFromRoot.remove(pathFromRoot.size() - 1); // Undo 
     return depth; 
    } 
} 

ein Illegal Werfen auf jeden Fall besser sein würde, aber mit diesem Code, den Sie vielleicht den Fehler schneller (oder nicht) finden.