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

### 题目:

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
/ \
1   3
```

### 解题思路:

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
}```

0 条评论

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

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

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

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

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

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

• ### LeetCode 337. 打家劫舍 III（记忆化+递归）

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

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

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

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

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

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

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

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

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