霍夫曼编码路径查找问题求助：如何正确获取节点路径？

问题分析 #

你的代码核心问题出在回溯逻辑错误和全局变量导致的状态混乱：

• 最后一个if条件的逻辑运算符优先级错误：node.left == null || node.right == null会优先执行，导致只要节点有一个子节点就触发删除操作，而非仅在遍历完子节点未找到目标时回溯。
• 全局变量mark和path在递归中状态管理混乱，无法准确跟踪每一层递归的路径状态。
• 回溯时机错误：应该在遍历完子节点且未找到目标时，才删除当前层添加的路径字符，而非仅针对叶子节点。

修复方案 #

改用递归返回布尔值标记是否找到目标，并使用StringBuilder（比String拼接更高效）维护路径，每一层递归独立处理路径的添加与回溯：

// encodes a message to binary
String encoder(char data) {
    StringBuilder path = new StringBuilder();
    findPath(root, data, path);
    return path.toString();
}

// finds the path to a node, returns true if found
boolean findPath(TNode node, char data, StringBuilder path) {
    if (node == null) {
        return false;
    }
    // 找到目标节点，返回true标记找到
    if (node.data == data) {
        return true;
    }

    // 遍历左子树：添加0，递归查找
    path.append('0');
    if (findPath(node.left, data, path)) {
        return true;
    }
    // 左子树没找到，回溯删除最后一位
    path.deleteCharAt(path.length() - 1);

    // 遍历右子树：添加1，递归查找
    path.append('1');
    if (findPath(node.right, data, path)) {
        return true;
    }
    // 右子树没找到，回溯删除最后一位
    path.deleteCharAt(path.length() - 1);

    // 当前节点的左右子树都没找到，返回false
    return false;
}

关键改进点 #

• 移除全局变量：用方法参数传递StringBuilder和返回布尔值，避免递归中的状态污染。
• 明确回溯逻辑：每遍历一个子节点前添加路径字符，若该子树未找到目标，则立即删除添加的字符，确保路径始终对应当前遍历的节点层级。
• 高效路径维护：StringBuilder的deleteCharAt比String.substring更高效，且避免创建大量临时String对象。
• 边界安全处理：增加node == null的判断，防止空指针异常。

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