采用递归方法实现这个代码
时间: 2023-10-26 20:19:39 浏览: 47
下面是采用递归方法实现二叉搜索树的查找代码:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
class BinarySearchTree:
def __init__(self):
self.root = None
def search(self, val):
return self._search_helper(val, self.root)
def _search_helper(self, val, node):
if not node or node.val == val:
return node
elif val < node.val:
return self._search_helper(val, node.left)
else:
return self._search_helper(val, node.right)
```
上面的代码中,`search` 方法调用了 `_search_helper` 方法进行查找。`_search_helper` 方法接收两个参数,分别为要查找的值和当前节点。如果当前节点为 `None` 或当前节点值等于要查找的值,返回当前节点;否则,根据当前节点值与要查找的值的大小关系,递归调用左子树或右子树的 `_search_helper` 方法。
这种方法相对于迭代方法来说,代码更加简洁,但是空间复杂度较高,可能会出现栈溢出的问题。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)