二叉搜索树（BST）大树性能异常及值存在判断函数实现求助

没问题，我来帮你搞定这个二叉搜索树的查找函数！先补全你的Node类，再提供两种实用的实现方式，完全适配你的需求。

第一步：完善Node类 #

首先把你写的Node类补全，加上构造函数方便创建节点：

class Node {
    public int value;
    public Node left, right;

    // 构造函数，初始化节点值和左右子节点
    public Node(int value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

第二步：实现contains函数 #

我们可以利用二叉搜索树的核心特性（左子树节点值全小于根，右子树节点值全大于根）来高效查找，不用遍历所有节点。这里提供两种常用实现：

方式1：递归实现（简洁直观）

递归版本代码量少，逻辑清晰，适合大多数场景：

public static boolean contains(Node root, int target) {
    // 基线条件：当前节点为空，说明没找到目标值
    if (root == null) {
        return false;
    }

    // 找到目标值，直接返回true
    if (root.value == target) {
        return true;
    }

    // 目标值小于当前节点值，去左子树递归查找
    if (target < root.value) {
        return contains(root.left, target);
    }
    // 目标值大于当前节点值，去右子树递归查找
    else {
        return contains(root.right, target);
    }
}

方式2：迭代实现（避免栈溢出）

如果你的二叉搜索树深度非常大，递归可能会触发栈溢出错误，这时候迭代版本更安全：

public static boolean containsIterative(Node root, int target) {
    Node currentNode = root;
    while (currentNode != null) {
        if (currentNode.value == target) {
            return true;
        }
        // 目标值更小，往左子树走
        else if (target < currentNode.value) {
            currentNode = currentNode.left;
        }
        // 目标值更大，往右子树走
        else {
            currentNode = currentNode.right;
        }
    }
    // 遍历完所有可能的节点都没找到，返回false
    return false;
}

针对你的示例验证 #

你提到的树结构：

• n1（value=1，左右子节点都为null）
• n2（value=2，左子节点是n1，右子节点是n3）
• n3（value=3，左右子节点都为null）

调用contains(n2, 3)时：

1. 初始节点是n2（value=2），3>2，所以转向右子节点n3
2. 当前节点变为n3，它的value正好等于目标值3，直接返回true，完全符合你的预期。

注意事项 #

• 这两个实现都依赖二叉搜索树的正确性：树必须严格满足左子树所有节点值 < 根节点值，右子树所有节点值 > 根节点值。如果你的树不符合这个规则，查找逻辑会出错。
• 如果你的业务场景允许二叉搜索树存在重复值，需要调整逻辑（比如允许重复值存左子树或右子树，查找时要对应遍历），不过你的示例里没有重复值，当前实现完全适用。

内容的提问来源于stack exchange，提问作者AV Legor