algorithm - 查找一个值是否包含在二叉树中

Question

我有一个 TreeNode 类，如下所示:

class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;

public TreeNode(int x) {
    value = x;
}

我想编写一个递归方法 contains(int i) 如果 i 是树中节点的值，它将返回 true，否则返回 false。

根据我的理解，二叉树不需要排序，所以我不应该将当前节点的值与我们正在搜索的值进行比较。因此我写了下面的方法:

public boolean contains(int i) {
    if (value == x) {
        return true;
    } else {
        if (left != null) {
            return left.find(i);
        }
        if (right != null) {
            return right.find(i);
        }
    }
    return false;
}

我的想法是，它会检查当前节点的值是否等于我们正在搜索的值，如果不相等，那么如果左右节点不为空，则它应该递归调用该方法，否则该方法将返回 false。

如果我们正在搜索对应于树左侧节点的值，此方法最终会返回 true，但是一旦我们搜索超出此值(向右)的值，它将返回 false。几个小时以来，我一直在思考这个问题，我确信有一个相对微不足道的解决方案，但我似乎做不到。

Answer 1

像这样:

public boolean contains(int i) {
    return value == i ||
       left != null && left.contains(i) ||
       right != null && right.contains(i);
}