LeetCode 700. 二叉搜索树中的搜索-阿里云开发者社区

开发者社区> freesan44> 正文

LeetCode 700. 二叉搜索树中的搜索

简介: 给定二叉搜索树(BST)的根节点和一个值。
+关注继续查看

题目

给定二叉搜索树(BST)的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在,则返回 NULL。

例如,

给定二叉搜索树:

        4
       / \
      2   7
     / \
    1   3

和值: 2
你应该返回如下子树:

      2     
     / \   
    1   3
在上述示例中,如果要找的值是 5,但因为没有节点值为 5,我们应该返回 NULL。

解题思路

class Solution:
    def searchBST(self, root: TreeNode, val: int) -> TreeNode:
        if root == None: return None#特例处理
        # stack = []
        # node = root
        # #先序遍历
        # while node or len(stack)!= 0:
        #     if node:
        #         stack.append(node)
        #         if node.val == val:
        #             return node
        #         node = node.left
        #     else:
        #         node = stack.pop()
        #         node = node.right
        # return None
        #根据搜索树的特性进行遍历
        node = root
        while node:
            if node.val > val:
                node = node.left
            elif node.val < val:
                node = node.right
            else:
                return node
        return None

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
LeetCode 145 Binary Tree Postorder Traversal(二叉树的后续遍历)+(二叉树、迭代)
版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/50933610 翻译 给定一个二叉树,返回其后续遍历的节点的值。
695 0
LeetCode 94 Binary Tree Inorder Traversal(二叉树的中序遍历)+(二叉树、迭代)
版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/50930671 翻译 给定一个二叉树,返回其中序遍历的节点的值。
728 0
LeetCode 235. 二叉搜索树的最近公共祖先
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
122 0
LeetCode 700. 二叉搜索树中的搜索
给定二叉搜索树(BST)的根节点和一个值。
85 0
对pos搜索函数的研究以及优化思路···
代码摘自delphi的Pos函数。。。总的来说,若我理解无误的话,该函数才用的搜索机制并不是非常高明。
600 0
看动画学算法之:平衡二叉搜索树AVL Tree
平衡二叉搜索树是一种特殊的二叉搜索树。为什么会有平衡二叉搜索树呢? 考虑一下二叉搜索树的特殊情况,如果一个二叉搜索树所有的节点都是右节点,那么这个二叉搜索树将会退化成为链表。从而导致搜索的时间复杂度变为O(n),其中n是二叉搜索树的节点个数。 而平衡二叉搜索树正是为了解决这个问题而产生的,它通过限制树的高度,从而将时间复杂度降低为O(logn)。
14 0
+关注
46
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载