[Leetcode][700. 二叉搜索树中的搜索] 3种方法：递归，迭代，BFS
By Long Luo
Leetcode 700. 二叉搜索树中的搜索 题目如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20700. 二叉搜索树中的搜索
给定二叉搜索树（BST）的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。返回以该节点为根的子树。 如果节点不存在，则返回NULL。
例如，
给定二叉搜索树:
4
/ \
2 7
/ \
1 3
和值: 2
你应该返回如下子树:
2
/ \
1 3
在上述示例中，如果要找的值是5，但因为没有节点值为5，我们应该返回NULL。
方法一：递归
思路与算法
首先想到的是递归，因为二叉搜索树的特点：
- 左子树所有节点的元素值均小于根的元素值；
- 右子树所有节点的元素值均大于根的元素值。
如果树为NULL或者节点值等于目标值，返回此节点。
代码如下所示：1
2
3
4
5
6
7
8
9
10
11public TreeNode searchBST(TreeNode root, int val) {
if (root == null || root.val == val) {
return root;
}
if (val < root.val) {
return searchBST(root.left, val);
} else {
return searchBST(root.right, val);
}
}
复杂度分析：
时间复杂度：\(O(N)\) ，其中 \(N\) 为二叉搜索树中的节点数。最坏情况下二叉搜索树是一条链，且要找的元素比链末尾的元素值还要小（大），这种情况下我们需要递归\(N\)次。
空间复杂度：\(O(N)\) ，递归需要 \(N\) 个函数栈，最坏情况下递归需要 \(O(N)\) 的栈空间。
方法二：迭代
思路与算法
既然可以使用递归，那么肯定也可以使用迭代实现。
代码如下所示：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15public TreeNode searchBST(TreeNode root, int val) {
if (root == null || root.val == val) {
return root;
}
while (root != null && root.val != val) {
if (root.val > val) {
root = root.left;
} else {
root = root.right;
}
}
return root;
}
复杂度分析：
时间复杂度：\(O(N)\) ，其中 \(N\) 为二叉搜索树中的节点数。最坏情况下二叉搜索树是一条链，且要找的元素比链末尾的元素值还要小（大），这种情况下我们需要迭代 \(N\) 次。
空间复杂度：\(O(1)\) ，没有使用额外的空间。
方法三：BFS
我们还可以使用BFS实现，代码如下所示：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22public TreeNode searchBST(TreeNode root, int val) {
if (root == null) {
return null;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (val == node.val) {
return node;
}
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
return null;
}
复杂度分析：
时间复杂度：\(O(N)\) ，其中 \(N\) 为二叉搜索树中的节点数。最坏情况下二叉搜索树是一条链，且要找的元素比链末尾的元素值还要小（大），这种情况下我们需要搜索 \(N\) 次。
空间复杂度：\(O(N)\) ，需要存储 \(N\) 个树节点。
All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)
Explore More Leetcode Solutions. 😉😃💗