Python二叉搜索树值存在检查函数的问题求助

嘿，我来帮你搞定这个二叉搜索树的contains函数问题！你的现有代码只检查了当前节点和直接子节点，还有逻辑错误，难怪过不了正确性和性能测试。先看看你的代码问题在哪：

import collections
class BinarySearchTree:
    Node = collections.namedtuple('Node', ['left', 'right', 'value'])
    @staticmethod
    def contains(root, value):
        if root.value == value:
            return True
        elif root.value < value:
            return root.right.value == value #I am using == to return True or False
        else:
            return root.right.value == value

现有代码的问题 #

• 逻辑错误：当目标值小于当前节点值时，应该去左子树查找，但你的代码里还是访问了root.right，完全搞反了二叉搜索树的核心性质！
• 只检查一层节点：不管是左还是右子树，你只判断了直接子节点的value，没有深入遍历下去，遇到稍微大一点的树肯定找不到深层的目标节点。
• 未处理空节点：如果当前节点的子节点是空的（比如叶子节点的子节点），访问root.right.value会直接抛出AttributeError。

修复后的代码（递归版本） #

递归版本逻辑清晰，适合理解BST的查找逻辑：

import collections
class BinarySearchTree:
    Node = collections.namedtuple('Node', ['left', 'right', 'value'])
    @staticmethod
    def contains(root, value):
        # 递归到空节点，说明没找到目标值
        if root is None:
            return False
        if root.value == value:
            return True
        elif root.value < value:
            # 目标值更大，去右子树继续查找
            return BinarySearchTree.contains(root.right, value)
        else:
            # 目标值更小，去左子树继续查找
            return BinarySearchTree.contains(root.left, value)

更适合大型树的迭代版本（性能更稳定） #

递归版本在树非常深的时候可能会触发栈溢出，迭代版本用循环实现，性能更稳定，适合处理大型树：

import collections
class BinarySearchTree:
    Node = collections.namedtuple('Node', ['left', 'right', 'value'])
    @staticmethod
    def contains(root, value):
        current = root
        while current is not None:
            if current.value == value:
                return True
            elif current.value < value:
                current = current.right
            else:
                current = current.left
        # 循环结束说明遍历完整个树都没找到目标值
        return False

为什么这样改？ #

• 处理空节点：不管是递归还是迭代，都先判断节点是否为空，避免属性访问错误。
• 严格遵循BST性质：按照“左子树值都小于当前节点，右子树值都大于当前节点”的规则，递归/迭代深入查找，不会走冤枉路。
• 完整遍历逻辑：直到找到目标值或者遍历完整个树（遇到空节点）才停止，确保能找到深层节点，也不会遗漏任何情况。

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