LeetCode 700. Search in a Binary Search Tree 题解

LeetCode 700. Search in a Binary Search Tree 题解题目描述给定二叉搜索树BST的根节点root和一个整数值val。你需要在 BST 中找到节点值等于val的节点。返回以该节点为根的子树。如果节点不存在则返回null。示例 1输入root [4,2,7,1,3], val 2 输出[2,1,3]示例 2输入root [4,2,7,1,3], val 5 输出[]解题思路方法一递归思路利用二叉搜索树的性质左子树的所有节点值小于根节点的值右子树的所有节点值大于根节点的值递归地搜索目标值如果当前节点为空返回null如果当前节点的值等于目标值返回当前节点如果当前节点的值大于目标值递归搜索左子树如果当前节点的值小于目标值递归搜索右子树复杂度分析时间复杂度O(h)其中 h 是二叉搜索树的高度。在最坏情况下二叉搜索树退化为链表时间复杂度为 O(n)。空间复杂度O(h)递归调用的栈空间取决于二叉搜索树的高度。方法二迭代思路使用迭代的方式利用二叉搜索树的性质搜索目标值当当前节点不为空且当前节点的值不等于目标值时如果当前节点的值大于目标值移动到左子节点如果当前节点的值小于目标值移动到右子节点当循环结束时返回当前节点复杂度分析时间复杂度O(h)其中 h 是二叉搜索树的高度。在最坏情况下二叉搜索树退化为链表时间复杂度为 O(n)。空间复杂度O(1)只需要常数级的额外空间。代码实现方法一递归# Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # self.val val # self.left left # self.right right class Solution: def searchBST(self, root: Optional[TreeNode], val: int) - Optional[TreeNode]: # 递归终止条件 if not root: return None # 如果当前节点的值等于目标值返回当前节点 if root.val val: return root # 如果当前节点的值大于目标值递归搜索左子树 elif root.val val: return self.searchBST(root.left, val) # 如果当前节点的值小于目标值递归搜索右子树 else: return self.searchBST(root.right, val)方法二迭代# Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # self.val val # self.left left # self.right right class Solution: def searchBST(self, root: Optional[TreeNode], val: int) - Optional[TreeNode]: current root while current: # 如果当前节点的值等于目标值返回当前节点 if current.val val: return current # 如果当前节点的值大于目标值移动到左子节点 elif current.val val: current current.left # 如果当前节点的值小于目标值移动到右子节点 else: current current.right # 如果节点不存在返回 None return None测试用例测试用例 1输入root [4,2,7,1,3], val 2输出[2,1,3]测试用例 2输入root [4,2,7,1,3], val 5输出[]总结本题是二叉搜索树的经典问题主要考察对二叉搜索树性质的理解和应用。通过使用递归或迭代我们可以高效地在二叉搜索树中搜索目标值。递归的核心思想是利用二叉搜索树的性质递归地搜索目标值。迭代的核心思想是使用循环的方式利用二叉搜索树的性质搜索目标值。在实际应用中迭代方法通常更受欢迎因为它的空间复杂度更低而且避免了递归调用的栈开销。这种方法不仅适用于二叉搜索树中的搜索问题还可以应用于许多其他需要在二叉搜索树中查找元素的场景。掌握这些方法对于解决这类问题非常重要。