java - 二叉树的高度 StackOverflow 异常

Question

我正在尝试在 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)
    ...
    ...
    ...

注意:我的树非常大，所以也许这就是原因？

有人可以帮我吗？谢谢!

Answer 1

当然，当您的树非常高时，可能会发生这种情况:每次调用 getHeight 都会创建一个堆栈帧，因此您面临着耗尽非常高的树的堆栈的风险。

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

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