【Leetcode算法题】700. 二叉搜索树中的搜索

By Long Luo

今天Leetcode的每日一题是:700. 二叉搜索树中的搜索,题目如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
700. 二叉搜索树中的搜索

给定二叉搜索树(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
11
public 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)O(N),其中NN为二叉搜索树中的节点数。最坏情况下二叉搜索树是一条链,且要找的元素比链末尾的元素值还要小(大),这种情况下我们需要递归NN次。

  • 空间复杂度:O(N)O(N),递归需要NN个函数栈,最坏情况下递归需要O(N)O(N)的栈空间。

方法二:迭代

思路与算法:

既然可以使用递归,那么肯定也可以使用迭代实现。

代码如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public 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)O(N),其中NN为二叉搜索树中的节点数。最坏情况下二叉搜索树是一条链,且要找的元素比链末尾的元素值还要小(大),这种情况下我们需要迭代NN次。

  • 空间复杂度:O(1)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
22
public 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)O(N),其中NN为二叉搜索树中的节点数。最坏情况下二叉搜索树是一条链,且要找的元素比链末尾的元素值还要小(大),这种情况下我们需要搜索NN次。

  • 空间复杂度:O(N)O(N),需要存储NN个树节点。