java - 递归搜索二叉树以查找字符串值

Question

我有一个二叉树，它应该只保存唯一的字符串值。在输入新字符串(由用户完成)之前，我需要递归检查树以查看该字符串是否已存在。这是我想出的方法，但它只是找到某些值(我认为是根值和左值)。任何有关如何解决此问题的提示都将受到赞赏!

public static TreeNode wordExists(TreeNode root, String strInput){
    if (root != null){

    if (strInput.equals(root.dataItem))
    {
        return root;
    }
    if (root.left != null){
        return wordExists (root.left, strInput);
    }
    if (root.right != null){
        return wordExists (root.right, strInput);
        }
    }
    return null;
}

Answer 1

当您向下导航每个分支时，您需要在返回结果之前检查结果。否则，如果结果仅在右侧分支中，但左侧分支中有其他非空值，则您将只返回 null，因为在左侧路径中找不到它。

所以而不是

if (root.left != null) {
    return wordExists(root.left, strInput);
}
if (root.right != null) {
    return wordExists(root.right, strInput);
}

你可能会做类似的事情

TreeNode result;
if ((result = wordExists(root.left, strInput)) != null) {
    return result;
}
return wordExists(root.right, strInput);

您可以在第二次递归时使用快捷方式，因为如果失败，您无论如何都会返回 null。