LeetCode 二叉搜索树搜索题解

LeetCode 二叉搜索树搜索题解

题目描述

实现二叉搜索树的搜索算法，在二叉搜索树中查找目标值。

示例：

输入：

4 / \ 2 6 / \ / \ 1 3 5 7

目标值：5
输出：找到节点5

解题思路

方法：二叉搜索树搜索

思路：

• 二叉搜索树的特点是：左子树的所有节点的值都小于根节点的值，右子树的所有节点的值都大于根节点的值。
• 利用这个特点，可以通过比较目标值与当前节点的值来决定搜索方向：
  1. 如果目标值等于当前节点的值，返回当前节点。
  2. 如果目标值小于当前节点的值，递归搜索左子树。
  3. 如果目标值大于当前节点的值，递归搜索右子树。
  4. 如果到达空节点，说明目标值不存在。

复杂度分析：

• 时间复杂度：O(h)，其中 h 是二叉搜索树的高度。在平衡二叉搜索树中，h = log n。
• 空间复杂度：O(h)，需要额外的空间来存储递归调用的栈。

代码实现

方法：二叉搜索树搜索（递归）

# 定义二叉搜索树节点 class TreeNode: def __init__(self, val=0, left=None, right=None): 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 是树的高度。

二叉搜索树搜索的核心思想是：利用二叉搜索树的特性，通过比较目标值与当前节点的值来决定搜索方向。

掌握二叉搜索树搜索的原理和实现，对于理解树形数据结构的搜索操作非常重要。