[Leetcode][700. 二叉搜索树中的搜索] 3种方法：递归，迭代，BFS

By Long Luo

Leetcode 700. 二叉搜索树中的搜索 题目如下：

700. 二叉搜索树中的搜索

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

例如，
给定二叉搜索树:

        4
       / \
      2   7
     / \
    1   3

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

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

方法一：递归

思路与算法

首先想到的是递归，因为二叉搜索树的特点：

• 左子树所有节点的元素值均小于根的元素值；
• 右子树所有节点的元素值均大于根的元素值。

如果树为NULL或者节点值等于目标值，返回此节点。

代码如下所示：

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

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

方法二：迭代

思路与算法

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

代码如下所示：

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)$，其中$N$为二叉搜索树中的节点数。最坏情况下二叉搜索树是一条链，且要找的元素比链末尾的元素值还要小（大），这种情况下我们需要迭代$N$次。

• 空间复杂度：$O(1)$，没有使用额外的空间。

方法三：BFS

我们还可以使用BFS实现，代码如下所示：

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)$，其中$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. 😉😃💗