LeetCode 二叉搜索树搜索题解题目描述实现二叉搜索树的搜索算法在二叉搜索树中查找目标值。示例输入4 / \ 2 6 / \ / \ 1 3 5 7目标值5输出找到节点5解题思路方法二叉搜索树搜索思路二叉搜索树的特点是左子树的所有节点的值都小于根节点的值右子树的所有节点的值都大于根节点的值。利用这个特点可以通过比较目标值与当前节点的值来决定搜索方向如果目标值等于当前节点的值返回当前节点。如果目标值小于当前节点的值递归搜索左子树。如果目标值大于当前节点的值递归搜索右子树。如果到达空节点说明目标值不存在。复杂度分析时间复杂度O(h)其中 h 是二叉搜索树的高度。在平衡二叉搜索树中h log n。空间复杂度O(h)需要额外的空间来存储递归调用的栈。代码实现方法二叉搜索树搜索递归# 定义二叉搜索树节点 class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right # 二叉搜索树搜索递归 def search_bst(root, val): if not root: return None if root.val val: return root elif root.val val: return search_bst(root.left, val) else: return search_bst(root.right, val) # 测试 def test_search_bst(): # 构建二叉搜索树 root TreeNode(4) root.left TreeNode(2) root.right TreeNode(6) root.left.left TreeNode(1) root.left.right TreeNode(3) root.right.left TreeNode(5) root.right.right TreeNode(7) # 测试搜索 result search_bst(root, 5) print(result.val if result else None) # 输出5 result search_bst(root, 8) print(result) # 输出None if __name__ __main__: test_search_bst()方法二叉搜索树搜索迭代# 二叉搜索树搜索迭代 def search_bst_iterative(root, val): current root while current: if current.val val: return current elif current.val val: current current.left else: current current.right return None # 测试 def test_search_bst_iterative(): # 构建二叉搜索树 root TreeNode(4) root.left TreeNode(2) root.right TreeNode(6) root.left.left TreeNode(1) root.left.right TreeNode(3) root.right.left TreeNode(5) root.right.right TreeNode(7) # 测试搜索 result search_bst_iterative(root, 5) print(result.val if result else None) # 输出5 result search_bst_iterative(root, 8) print(result) # 输出None if __name__ __main__: test_search_bst_iterative()测试用例测试用例 1基本情况输入4 / \ 2 6 / \ / \ 1 3 5 7目标值5输出找到节点5测试用例 2目标值不存在输入4 / \ 2 6 / \ / \ 1 3 5 7目标值8输出None总结二叉搜索树搜索是一种高效的搜索算法它利用二叉搜索树的特性来快速定位目标值。二叉搜索树搜索的时间复杂度为 O(h)其中 h 是树的高度。二叉搜索树搜索的核心思想是利用二叉搜索树的特性通过比较目标值与当前节点的值来决定搜索方向。掌握二叉搜索树搜索的原理和实现对于理解树形数据结构的搜索操作非常重要。