Javaのバイナリ検索ツリーを走査中のStackOverflowError

Question

BSTの最も深いノードを返すメソッドがあります。なぜそれがエラーを上げている、それが正常に見える私に

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

：私はStackOverflowのエラーを発生させ、このコードを持っていますか？

Answer 1

getDeepestNodeはスタック上で繰り返し発生する必要があります。

おそらくAVLツリーに1つのサイクルがあります。命名、headは、既に汚れた考えを示すかもしれません。デバッグが役立ちます。また、あなたのようにあなたのコードを固めるかもしれません ：

IllegalStateExceptionがを投げる

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

は間違いなく良いだろうが、このコードで、あなたはより速く（またはしない）エラーを見つけるかもしれません。