判断输入的一棵二叉树是否是二叉搜索树
时间: 2023-04-28 09:01:01 浏览: 84
判断一棵二叉树是否是二叉搜索树,需要满足以下条件:
1. 左子树中所有节点的值都小于根节点的值;
2. 右子树中所有节点的值都大于根节点的值;
3. 左子树和右子树都必须是二叉搜索树。
因此,可以通过递归的方式判断每个节点是否满足以上条件,如果满足则继续递归判断其左右子树,否则返回false。
具体实现可以参考以下代码:
```
class TreeNode:
def __init__(self, val=, left=None, right=None):
self.val = val
self.left = left
self.right = right
def isValidBST(root: TreeNode) -> bool:
def helper(node, lower=float('-inf'), upper=float('inf')):
if not node:
return True
val = node.val
if val <= lower or val >= upper:
return False
if not helper(node.right, val, upper):
return False
if not helper(node.left, lower, val):
return False
return True
return helper(root)
```
其中,helper函数用于递归判断每个节点是否满足条件,lower和upper分别表示当前节点的值应该在的范围。如果当前节点的值不在该范围内,则返回false。如果当前节点满足条件,则继续递归判断其左右子树是否也满足条件。最后,如果整棵树都满足条件,则返回true。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pptx](https://img-home.csdnimg.cn/images/20210720083543.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)