java - 二叉树StackOverflow异常的高度

我试图在Java中查找二进制搜索树的高度。这是我的getHeight()函数。

public int getHeight(RedBlackTree<E> n) {
    if (n == EMPTY || n == null) // line 427
        return -1;
    return 1 + Math.max(getHeight(n.left), getHeight(n.right)); // line 429
}

我不断收到StackOverflow异常：

Exception in thread "AWT-EventQueue-0" java.lang.StackOverflowError
    at RedBlackTree.getHeight(RedBlackTree.java:427)
    at RedBlackTree.getHeight(RedBlackTree.java:429)
    at RedBlackTree.getHeight(RedBlackTree.java:429)
    at RedBlackTree.getHeight(RedBlackTree.java:429)
    at RedBlackTree.getHeight(RedBlackTree.java:429)
    ...
    ...
    ...

注意：我的树很大，所以也许这是为什么？

有人可以帮我吗？谢谢！

最佳答案

当然，这可能在您的树很高时发生：每次调用getHeight都会创建一个堆栈框架，因此您冒着耗尽非常高的树的堆栈的风险。

如果您的图形有一个循环，也可能发生这种情况，这意味着它实际上不是一棵树。您可以通过将到目前为止已访问的树的所有顶点存储在HashSet中来测试是否是这种情况。如果在计算树高的过程中第二次看到顶点，则有一个带有循环的图形。

解决堆栈溢出问题的一种方法是使用您自己的集合，堆栈或队列，以迭代方式计算高度。