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 值，则您将返回 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 。