AVL树递归求节点高度函数遇StackOverflowError问题求助

嗨，你猜的完全没错！这个StackOverflowError就是递归实现惹的祸，我来给你掰扯清楚问题根源和解决办法～

为啥会爆栈？ #

Java的每个线程都有自己的栈空间，默认大小一般在1-2MB左右，每一次递归调用都会在栈里生成一个栈帧。AVL树虽然是平衡树，高度是*O(log n)*的，但当节点数足够多的时候（比如几十万甚至上百万），递归调用的深度会慢慢逼近栈的容量上限，栈帧堆得太多就直接炸了——这就是你看到异常指向那两行递归代码的原因。

最靠谱的解决方案：改成迭代实现 #

把递归的高度计算换成迭代方式，用栈或者队列遍历树，完全绕开递归的栈帧限制。给你两种常用的写法：

方法一：广度优先（层次遍历）

思路特别直观，一层一层数树的层数，层数就是树的高度：

public int height() {
    if (this == null) {
        return 0;
    }
    Queue<Node> queue = new LinkedList<>();
    queue.add(this);
    int height = 0;
    while (!queue.isEmpty()) {
        int levelNodeCount = queue.size();
        // 遍历当前层所有节点，把下一层节点入队
        for (int i = 0; i < levelNodeCount; i++) {
            Node current = queue.poll();
            if (current.left != null) {
                queue.add(current.left);
            }
            if (current.right != null) {
                queue.add(current.right);
            }
        }
        height++; // 每遍历完一层，高度加1
    }
    return height;
}

方法二：深度优先（迭代版）

用栈模拟递归过程，记录每个节点的深度，跟踪最大深度：

public int height() {
    if (this == null) {
        return 0;
    }
    Stack<NodeDepthPair> stack = new Stack<>();
    stack.push(new NodeDepthPair(this, 1));
    int maxHeight = 0;
    while (!stack.isEmpty()) {
        NodeDepthPair pair = stack.pop();
        Node current = pair.node;
        int currentDepth = pair.depth;
        
        if (currentDepth > maxHeight) {
            maxHeight = currentDepth;
        }
        // 先压右节点再压左，保证左节点先被处理（和递归顺序一致）
        if (current.right != null) {
            stack.push(new NodeDepthPair(current.right, currentDepth + 1));
        }
        if (current.left != null) {
            stack.push(new NodeDepthPair(current.left, currentDepth + 1));
        }
    }
    return maxHeight;
}

// 辅助类，用来存储节点和对应的深度
class NodeDepthPair {
    Node node;
    int depth;
    public NodeDepthPair(Node node, int depth) {
        this.node = node;
        this.depth = depth;
    }
}

终极优化：给AVL节点缓存高度 #

其实AVL树的标准实现里，每个节点本来就应该维护一个height属性！每次插入、删除、旋转操作时，同步更新相关节点的高度值，这样获取高度直接返回缓存值，*O(1)*时间复杂度，彻底解决问题还能大幅提升性能：

class Node {
    int val;
    Node left;
    Node right;
    int height; // 维护当前节点的高度，叶子节点初始为1

    public Node(int val) {
        this.val = val;
        this.height = 1;
    }

    // 直接返回缓存的高度，再也不用递归/迭代计算了
    public int height() {
        return this.height;
    }
}

比如在旋转操作后，只需要重新计算父节点的高度：node.height = Math.max(node.left.height, node.right.height) + 1，这样所有操作都能同步维护高度，既高效又不会爆栈。

不推荐的临时方案：调大JVM栈 #

如果你非要坚持用递归，可以通过JVM参数-Xss增大栈容量，比如-Xss4m，但这只是饮鸩止渴——栈太大会占用过多内存，而且当树足够大的时候还是会爆栈，完全不如上面的方法靠谱。

内容的提问来源于stack exchange，提问作者petergx