如果在树中没有找到输入，我如何使这个递归二叉树遍历返回null ?

Question

我不确定如何使此递归方法返回null，如果字符不存在于树中。

BinaryTreeNode<CharData> answer; // Declare answer variable to use in findChar method
public BinaryTreeNode<CharData> findChar(char ch, BinaryTreeNode<CharData> root){
// Base Case
if (root.getValue().getChar() == ch){
        answer =  root; // If the node "root" contains the character, then answer becomes root node. 
    }
    // Otherwise finish pre-order traversal
else {
    // Check that left child is not null. If not, recursive call for left child.
    if(root.getLeft() != null){
        findChar(ch, root.getLeft());
    }
    // Check that right child is not null. If not, recursive call for right child. 
    if(root.getRight() != null)
        findChar(ch, root.getRight());
    }
    return answer;
}

据我所知，answer必须在方法之外声明，以便返回任何内容。

然而，问题是，当我使用for循环来搜索列表字符和一些不存在于二进制树中，为这些不存在的字符返回的答案值是任何值为答案是在二叉树中存在的列表中的前一个字符。我更希望这个方法为这些值返回null。

Answer 1

几点观察1. 全局声明的answer是一个问题，有几个原因。2. 您错过了另一个情况:即当root是null时。3.findChar返回一个值，您可以使用它。4. 你没有利用你有一个搜索树的事实并且总是遍历整个树。我在这里假设它确实是一个搜索树，否则使用树就没有意义了。

所以我建议这样做:

public BinaryTreeNode<CharData> findChar(char ch, BinaryTreeNode<CharData> root){
    if (root == null) {
        return null;
    }
    if (root.getValue().getChar() == ch){
        return root;
    }
    if (root.getValue().getChar() > ch) {
        return findChar(ch, root.getLeft());
    } else {
        return findChar(ch, root.getRight());
    }
}

如果它不是一个二叉搜索树，像这样的东西将工作:

public BinaryTreeNode<CharData> findChar(char ch, BinaryTreeNode<CharData> root){
    if (root == null) {
        return null;
    }
    if (root.getValue().getChar() == ch){
        return root;
    }
    BinaryTreeNode<CharData> answer = findChar(ch, root.getLeft());
    if (answer != null) {
        return answer;
    } else {
        return findChar(ch, root.getRight());
    }
}