[Leetcode][700. 二叉搜索树中的搜索] 3种方法:递归,迭代,BFS
By Long Luo
Leetcode 700. 二叉搜索树中的搜索 题目如下:
1 | 700. 二叉搜索树中的搜索 |
方法一:递归
思路与算法
首先想到的是递归,因为二叉搜索树的特点:
- 左子树所有节点的元素值均小于根的元素值;
- 右子树所有节点的元素值均大于根的元素值。
如果树为NULL或者节点值等于目标值,返回此节点。
代码如下所示:
1 | public TreeNode searchBST(TreeNode root, int val) { |
复杂度分析:
-
时间复杂度:,其中为二叉搜索树中的节点数。最坏情况下二叉搜索树是一条链,且要找的元素比链末尾的元素值还要小(大),这种情况下我们需要递归次。
-
空间复杂度:,递归需要个函数栈,最坏情况下递归需要的栈空间。
方法二:迭代
思路与算法
既然可以使用递归,那么肯定也可以使用迭代实现。
代码如下所示:
1 | public TreeNode searchBST(TreeNode root, int val) { |
复杂度分析:
-
时间复杂度:,其中为二叉搜索树中的节点数。最坏情况下二叉搜索树是一条链,且要找的元素比链末尾的元素值还要小(大),这种情况下我们需要迭代次。
-
空间复杂度:,没有使用额外的空间。
方法三:BFS
我们还可以使用BFS实现,代码如下所示:
1 | public TreeNode searchBST(TreeNode root, int val) { |
复杂度分析:
-
时间复杂度:,其中为二叉搜索树中的节点数。最坏情况下二叉搜索树是一条链,且要找的元素比链末尾的元素值还要小(大),这种情况下我们需要搜索次。
-
空间复杂度:,需要存储个树节点。
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. 😉😃💗