专栏首页爱写BugLeetCode 700: 二叉搜索树中的搜索 Search in a Binary Search Tree

LeetCode 700: 二叉搜索树中的搜索 Search in a Binary Search Tree

题目:

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

Given the root node of a binary search tree (BST) and a value. You need to find the node in the BST that the node's value equals the given value. Return the subtree rooted with that node. If such node doesn't exist, you should return NULL.

例如,

给定二叉搜索树:

        4
       / \
      2   7
     / \
    1   3

和值: 2

你应该返回如下子树:

      2     
     / \   
    1   3

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

解题思路:

二叉搜索树中的搜索操作, 可根据 BST 的特性,对于每个节点:

  1. 如果目标值等于节点的值,则返回节点;
  2. 如果目标值小于节点的值,则继续在左子树中搜索;
  3. 如果目标值大于节点的值,则继续在右子树中搜索。

递归法:

Java:

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null)
            return null;
        if (val == root.val)
            return root;
        if (val > root.val)
            return searchBST(root.right, val);
        else
            return searchBST(root.left, val);
    }
}

Python:

class Solution:
    def searchBST(self, root: TreeNode, val: int) -> TreeNode:
        if not root:
            return None
        if val == root.val:
            return root
        if val > root.val:
            return self.searchBST(root.right, val)
        else:
            return self.searchBST(root.left, val)

Golang:

func searchBST(root *TreeNode, val int) *TreeNode {
    if root == nil {
        return nil
    }
    if root.Val == val {
        return root
    }
    if val > root.Val {
        return searchBST(root.Right, val)
    } else {
        return searchBST(root.Left, val)
    }
}

迭代法:

Java:

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        while(root!=null){
            if (root.val == val)
                return root;
            if (val > root.val)
                root=root.right;
            else
                root=root.left;
        }
        return null;
    }
}

Python:

class Solution:
    def searchBST(self, root: TreeNode, val: int) -> TreeNode:
        while root:
            if root.val == val:
                return root
            if val > root.val:
                root = root.right
            else:
                root = root.left
        return None

Golang:

func searchBST(root *TreeNode, val int) *TreeNode {
    for root != nil {
        if root.Val == val {
            return root
        }
        if val > root.Val {
            root = root.Right
        } else {
            root = root.Left
        }
    }
    return nil
}

本文分享自微信公众号 - 爱写Bug(iCodeBugs),作者:爱写Bug

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-03-16

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 二叉树的最近公共祖先 Lowest Common Ancestor of a Binary Tree

    Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in...

    爱写bug
  • LeetCode 450: 删除二叉搜索树中的节点 Delete Node in a BST

    给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节...

    爱写bug
  • LeetCode 701: 二叉搜索树中的插入操作 Insert into a Binary Search Tree

    给定二叉搜索树(BST)的根节点和要插入树中的值,将值插入二叉搜索树。返回插入后二叉搜索树的根节点。保证原始二叉搜索树中不存在新值。

    爱写bug
  • LeetCode 337. 打家劫舍 III(记忆化+递归)

    在上次打劫完一条街道之后和一圈房屋后,小偷又发现了一个新的可行窃的地区。这个地区只有一个入口,我们称之为“根”。 除了“根”之外,每栋房子有且只有一个“父“房子...

    Michael阿明
  • 程序员面试金典 - 面试题 04.05. 合法二叉搜索树(中序遍历)

    Michael阿明
  • 二叉树的最近公共祖先 Lowest Common Ancestor of a Binary Tree

    Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in...

    爱写bug
  • LeetCode 965. 单值二叉树

    Michael阿明
  • 014.Docker Harbor+Keepalived+LVS+共享存储高可用架构

    共享后端存储是一种比较标准的方案,将多个Harbor实例共享同一个后端存储,任何一个实例持久化到存储的镜像,都可被其他实例中读取。通过前置LB组件,如Keepa...

    木二
  • LeetCode 450: 删除二叉搜索树中的节点 Delete Node in a BST

    给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节...

    爱写bug
  • 利用rbd命令把 ceph pool 中的一个镜像导出

    查看镜像 [root@node1 ~]# rbd ls images a56330e7-79d7-4639-a68f-366ac344bfe2 eccfee07...

    院长技术

扫码关注云+社区

领取腾讯云代金券