哈夫曼编码路径构建时出现StackOverflowError异常求助

嘿，我一眼就看到你代码里的问题啦——这是个典型的无限递归导致栈溢出的情况！咱们先理清楚问题出在哪：

抛出异常信息：java.lang.StackOverflowError at java.lang.AbstractStringBuilder.ensureCa...

你的代码：

public String findPath(short target, int root, String path) { 
    String result; 
    if (root < 0) { 
        if ((result = findPath(target, root, path + '0')) == null) { 
            result = findPath(target, root, path + '1'); 
        } 
    } else { 
        result = (target == this.LEAF_NODES[root]) ? path : null; 
        System.out.println("? " + result); 
    } 
    return result; 
}

问题根源 #

当root < 0（也就是当前节点是非叶子节点）时，你递归调用findPath时传入的还是同一个root值！这就意味着递归永远不会往下走——每次都卡在同一个非叶子节点，无限重复调用自己，直到JVM的栈内存被耗尽，直接抛出StackOverflowError。

哈夫曼树的非叶子节点肯定是有左、右子节点的，你得在递归时传入当前节点的子节点索引，而不是原地打转。

修复方案 #

首先你需要一个存储非叶子节点子节点的结构，比如一个二维数组NON_LEAF_NODES，每个元素存对应非叶子节点的左、右孩子索引。然后修改递归逻辑，传入正确的子节点：

// 先定义存储非叶子节点左右子节点的数组，根据你的哈夫曼树结构初始化
private int[][] NON_LEAF_NODES; 

public String findPath(short target, int root, String path) { 
    String result; 
    if (root < 0) { 
        // 将负的root转换为非叶子节点数组的索引（比如root=-1对应索引0，依此类推）
        int nodeIdx = -root - 1;
        // 先递归左子树，路径追加'0'
        if ((result = findPath(target, NON_LEAF_NODES[nodeIdx][0], path + '0')) == null) { 
            // 左子树没找到，再递归右子树，路径追加'1'
            result = findPath(target, NON_LEAF_NODES[nodeIdx][1], path + '1'); 
        } 
    } else { 
        result = (target == this.LEAF_NODES[root]) ? path : null; 
        // System.out.println("? " + result); // 可以保留，但频繁打印会影响性能
    } 
    return result; 
}

额外优化：用StringBuilder优化路径拼接 #

每次用path + '0'都会创建新的String对象，递归次数多的话会产生大量临时对象，既耗内存又影响性能。换成StringBuilder来做路径拼接会更高效：

// 对外暴露的方法，初始化StringBuilder
public String findPath(short target, int root) { 
    StringBuilder pathBuilder = new StringBuilder();
    return findPathHelper(target, root, pathBuilder);
}

// 内部递归辅助方法
private String findPathHelper(short target, int root, StringBuilder path) { 
    String result; 
    if (root < 0) { 
        int nodeIdx = -root - 1;
        // 递归左子树：追加'0'
        path.append('0');
        result = findPathHelper(target, NON_LEAF_NODES[nodeIdx][0], path);
        if (result == null) {
            // 左子树没找到，回溯删除最后一个字符
            path.deleteCharAt(path.length() - 1);
            // 递归右子树：追加'1'
            path.append('1');
            result = findPathHelper(target, NON_LEAF_NODES[nodeIdx][1], path);
            if (result == null) {
                // 右子树也没找到，继续回溯
                path.deleteCharAt(path.length() - 1);
            }
        }
    } else { 
        result = (target == this.LEAF_NODES[root]) ? path.toString() : null; 
    } 
    return result; 
}

这样修改后，递归会正常遍历哈夫曼树的子节点，要么找到目标叶子节点返回路径，要么遍历完所有分支返回null，不会再出现无限递归的情况啦。

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