java - 使用dfs的递归树加密方法

Question

这个问题不适用于作业，尽管这是一个典型的“类似作业”问题，我正在尝试以不同的方式解决它。

我想编写一种方法，使用深度优先搜索算法递归地遍历二叉树来查找字符的匹配项。一旦找到匹配的字符，我希望它返回一个字符串，该字符串使用 0 和 1 映射该字符在树中的位置。例如，“001”表示通过转到根节点的左节点、该节点的左节点、然后到该节点的右节点来找到该字符。

这是我到目前为止的代码:

private static String encryptSearch(char c, BinaryNode curNode, String result)
{
    char data = (char) curNode.getData();

    if (data != c)
    {
        if (curNode.hasLeftChild())
        {
            result = result + "0";
            encryptSearch(c, curNode.getLeftChild(), result);
        }
        if (curNode.hasRightChild())
        {
            result = result + "1";
            encryptSearch(c, curNode.getRightChild(), result);  
        }

        result = result.substring(0, result.length()-1);
    }   

    return result;  
} 

该方法最初发送要搜索的字符、根节点和结果为 null。该方法除了 0 之外不返回任何内容。我认为我的代码存在多个问题，但最大的一个是当搜索到达叶节点时，它返回。我一直无法想出解决这个问题的方法，同时仍然返回一个字符串。我可以轻松编写一个 void 方法，将结果字符串作为外部变量进行操作，但我不想为了练习的目的而这样做。如有任何帮助，我们将不胜感激!

Answer 1

使用可变的 StringBuilder 而不是 String。另外，应该有一种方法可以知道在搜索右侧结果之前您是否从左侧结果(如果有)中获得了结果。所以我建议进行以下更改。

private static boolean encryptSearch(char c, BinaryNode curNode, StringBuilder result) {
    char data = curNode.getData();
    if (data != c) {
        boolean found = false;
        if (curNode.hasLeftChild()) {
            found = encryptSearch(c, curNode.getLeftChild(), result);
            if (found) {
                result.insert(0, "0");
                return true;
            }
        }
        if (curNode.hasRightChild()) {
            found = encryptSearch(c, curNode.getRightChild(), result);
            if (found) {
                result.insert(0, "1");
                return true;
            }
        }
        return false; //no result
    }
    return true;
}