【代码随想录day20】二叉搜索树中的搜索

小小的香辛料

于 2023-07-26 15:14:36 发布

阅读量215

点赞数

分类专栏：代码随想录 LeetCode 数据结构文章标签： python 算法 leetcode

本文链接：https://blog.csdn.net/doubleguy/article/details/131939594

版权

LeetCode 同时被 3 个专栏收录

112 篇文章

订阅专栏

数据结构

97 篇文章

订阅专栏

代码随想录

61 篇文章

订阅专栏

给定一个二叉搜索树的根节点和一个整数值，文章描述了如何通过比较节点值来递归或迭代地搜索目标节点。当找到目标节点时返回其子树，否则返回null。搜索过程中，如果值小于当前节点，则搜索左子树；如果值大于当前节点，则搜索右子树。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目

给定二叉搜索树（BST）的根节点 root 和一个整数值 val。

你需要在 BST 中找到节点值等于 val 的节点。返回以该节点为根的子树。如果节点不存在，则返回 null 。

示例 1:

思路

因为这里是二叉排序树，所以不用爆搜所有节点，只需要用val与当前节点进行比较，如果比当前节点大就搜索当前节点的右子树，如果比当前节点小就搜索当前节点的左子树，只要找到val直接返回root，或者root为空说明搜到树底都没有val，直接返回空。

递归写法

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         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 
        if val==root.val:
            return root
        return self.searchBST(root.left,val) if val<root.val else self.searchBST(root.right,val)

迭代写法

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         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 
        while root:
            if val==root.val:
                return root
            if root.val<val:
                root = root.right
            else:
                root = root.left