计算二叉搜索树平均深度时出现栈溢出错误，请求技术帮助

问题描述 #

我正在尝试计算二叉搜索树（BST）的平均深度，已经在BST类中实现了totalDepth方法：

int totalDepth(Node node, int depth) { 
    if(node == null) { 
        return 0; 
    } 
    return depth // myself + totalDepth(node.left, depth + 1) // my left subtree + totalDepth(node.right, depth + 1); // my right subtree 
}

但在main方法中执行这条打印语句时出现了栈溢出错误：

System.out.println("Average Depth : "+tree.totalDepth(tree.root,0)/10000);

希望能得到解决这个问题的帮助。

问题分析与解决方案 #

栈溢出的核心原因是递归深度超过了JVM的栈容量限制——如果你的BST是一棵极度不平衡的树（比如退化成了链表），递归调用的层数会等于树的节点数（10000个节点的话就是10000层递归），而JVM默认的栈深度一般在几千到几万之间（不同环境有差异），10000层很容易触发栈溢出。

下面给你两种可行的解决思路：

1. 改用迭代方式（推荐） #

把递归改成迭代，用队列或栈模拟递归过程，彻底摆脱JVM栈大小的限制：

import java.util.LinkedList;
import java.util.Queue;
import javafx.util.Pair; // 或者自己实现一个简单的Pair类

int totalDepthIterative(Node root) {
    if (root == null) {
        return 0;
    }
    int total = 0;
    // 用队列实现层序遍历，每个元素存储节点和对应的深度
    Queue<Pair<Node, Integer>> queue = new LinkedList<>();
    queue.add(new Pair<>(root, 0));
    
    while (!queue.isEmpty()) {
        Pair<Node, Integer> current = queue.poll();
        Node node = current.getKey();
        int depth = current.getValue();
        total += depth;
        
        if (node.left != null) {
            queue.add(new Pair<>(node.left, depth + 1));
        }
        if (node.right != null) {
            queue.add(new Pair<>(node.right, depth + 1));
        }
    }
    return total;
}

如果不想依赖javafx.util.Pair，可以自己写一个简单的内部类：

private class NodeDepthPair {
    Node node;
    int depth;
    NodeDepthPair(Node node, int depth) {
        this.node = node;
        this.depth = depth;
    }
}

之后在main方法里调用迭代版本即可：

System.out.println("Average Depth : "+tree.totalDepthIterative(tree.root)/10000);

2. 临时调整JVM栈大小 #

如果你坚持要用递归，可以通过JVM启动参数增大栈容量，比如：

-Xss2m

这个参数把栈大小设置为2MB（默认一般是1MB左右），足够支撑10000层的递归调用。不过这个方案有局限性：如果节点数继续增加（比如10万），还是会溢出，而且不同环境的JVM对栈大小的限制也不一样，通用性远不如迭代方案。

额外提示 #

计算平均深度时，建议先准确统计节点总数再做除法，避免出现除零错误或结果不准确的情况：

int countNodes(Node root) {
    if (root == null) return 0;
    return 1 + countNodes(root.left) + countNodes(root.right);
}

当然，节点统计也可以用迭代方式实现，避免同样的栈溢出问题。

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