二叉树的递归遍历不在返回语句处终止

Question

我创建了一个用摩尔斯电码填充二叉树的类。向左移动表示 DOT，向右移动表示 DASH。一切都很顺利，直到我编写一个编码方法将字母字符转换为莫尔斯电码字符串。该方法应该递归地对树进行预序遍历（沿途创建摩尔斯电码字符串），直到找到目标字符，然后返回该字符串。

但是，由于某种原因，我的递归不会在我的基本情况下终止。它只是继续运行整个遍历。我附上了下面方法的代码。为什么if语句中的return语句没有触发并结束方法？

抱歉，如果这有歧义，但我不想为我的整个项目发布 300 行代码，因为比我聪明的人会立即注意到问题。

感谢您的帮助

    //wrapper class
    //@parameter character is the character to be encoded
    //@return return the morse code as a string corresponding to the character

    public String encode(char character){

        return encode(morseTree, character, "");


    }


    //@Parameters tree is the binary tree is the tree to be searched, 
    //element is the target character trying to be foudn, s is the string being used to build the morse code
    //@return returns the morse code that corresponds to the element being checked

    public String encode(BinaryTree<Character> tree, char target, String s){


        if(tree.getData() == target){  //if the data at the current tree is equal to the target element
            //return the string that is holding the morse code pattern for this current traversal
            return s;
        }else{
            if(tree.getLeftSubtree() != null){
                    //Traverse the left side, add a DOT to the end of a string to change the morse code
                    encode(tree.getLeftSubtree(), target, s + DOT);
            }

            if(tree.getRightSubtree() != null){
                    //Traverse the left side, add a DOT to the end of a string to change the morse code
                    encode(tree.getRightSubtree(), target, s + DASH);
            }
        }

        //The code should never get this far!
        return s;
    }

Answer 1

您在 else 块中的调用不会返回 - 它们可能应该像这样：

if (tree.getLeftSubtree() != null) {
   // Traverse the left side, add a DOT to the end of a string to
   // change the morse code
   return encode(tree.getLeftSubtree(), target, s + DOT);
}

if (tree.getRightSubtree() != null) {
    // Traverse the left side, add a DOT to the end of a string to
    // change the morse code
    return encode(tree.getRightSubtree(), target, s + DASH);
}

但是，如果左子树和右子树都为空，您希望发生什么？如果它们都是非空，你想返回什么？

请注意，仅仅因为您的基本调用已经返回，所以仅返回该单个调用 - 而不是堆栈中的所有其他调用。递归不会用新调用替换堆栈帧 - 它只是添加另一个堆栈帧¹。从新的堆栈帧返回只会让您回到原来的位置。

---

¹ 是的，我知道尾递归。不过，我们不要混淆事情。