在Java中遍历二进制搜索树时发生StackOverflow错误

Question

我有一个返回BST中最深节点的方法。我有一段代码，它会引发StackOverflow错误：

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

对我来说，它看起来很好，为什么它会引发错误？

Answer 1

getDeepstNode必须在堆栈上重复出现。

你很可能在AVL树中有一个循环。命名head可能已经表明了不干净的思想。调试有帮助。或者，您可以将代码强化为：

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

抛出IllegalStateException肯定会更好，但使用此代码，您可能会更快（或不更快）发现错误。