基于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;
}