Java四叉树预序遍历转树结构时递归栈溢出问题求解

问题根源 #

递归构建四叉树时，当处理大规模数据（如79917个元素的预序遍历数组），JVM的调用栈会被耗尽，触发StackOverflowError。JVM默认栈空间有限（通常几百KB到几MB），递归深度一旦超过栈能容纳的调用层数就会报错——你的递归方法在小数据量下正常，就是因为此时递归深度未超出栈的承载上限。

核心解决方案：改用迭代实现 #

手动维护堆上的栈结构，模拟递归调用的上下文（当前父节点、处理索引、剩余待创建子节点数），彻底摆脱JVM调用栈的限制（堆内存远大于栈内存）。

以下是迭代版本的实现代码：

public void createQT(Integer[] numbers) {
    if (numbers == null || numbers.length == 0) {
        return;
    }
    // 栈元素存储处理上下文：当前父节点、当前索引、剩余需创建的子节点数量
    Stack<Object[]> stack = new Stack<>();
    // 初始状态：从索引1开始，以root为父节点，需创建1个子节点
    stack.push(new Object[]{root, 1, 1});

    while (!stack.isEmpty()) {
        Object[] context = stack.pop();
        QTNode currentParent = (QTNode) context[0];
        int index = (int) context[1];
        int remainingChildren = (int) context[2];

        if (remainingChildren == 0 || index >= numbers.length || numbers[index] == null) {
            continue;
        }

        QTNode node = new QTNode();
        currentParent.addChild(node);

        if (numbers[index] != -1) {
            // 叶子节点：设置强度后，继续处理父节点的下一个子节点
            node.setIntensity(numbers[index]);
            stack.push(new Object[]{currentParent, index + 1, remainingChildren - 1});
        } else {
            // 非叶子节点：先放回父节点的剩余任务，再倒序压入4个子节点任务（保证处理顺序与递归一致）
            stack.push(new Object[]{currentParent, index + 1, remainingChildren - 1});
            for (int i = 3; i >= 0; i--) {
                stack.push(new Object[]{node, index + 1, 1});
            }
        }
    }
}

代码说明 #

• 栈上下文设计：每个栈元素包含三个核心信息，确保能准确延续原递归逻辑的处理流程。
• 叶子节点处理：创建节点并设置强度后，将父节点的剩余子节点创建任务重新压入栈，推进索引并减少剩余数量。
• 非叶子节点处理：先放回父节点的未完成任务，再倒序压入4个子节点的创建任务——由于栈是后进先出结构，倒序压入能保证子节点的处理顺序与原递归完全一致。

临时应急方案（不推荐长期使用） #

若仅需临时测试，可通过JVM启动参数调整栈大小，例如-Xss4m（将栈容量设置为4MB）。但这只是治标之法，当数据量进一步增大时仍会触发栈溢出，迭代实现才是通用解决方案。

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