LeetCode 98 验证二叉搜索树(递归,中序遍历)
题目链接:验证二叉搜索树
给定一个二叉树,判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征:
- 节点的左子树只包含小于当前节点的数。
- 节点的右子树只包含大于当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
输入:
2
/ \
1 3
输出: true
示例 2:
输入:
5
/ \
1 4
/ \
3 6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
根节点的值为 5 ,但是其右子节点值为 4 。
思路
方法一:
首先考虑递归的解法,要保证满足二叉搜索树的条件。需要保证左子树的每一个值都要小于当前节点,右子树的每一个值,都要大于当前节点。我们可以维护一个最小值和最大值的范围,当一个点满足小于最大值且大于最小值就是一颗BST。
方法二:
对这棵树进行一次中序遍历,如果是一颗BST,那么遍历结果肯定是一个递增的序列,我们检查一下这个序列是不是递增的即可。
代码
方法一:
|
|
方法二:
|
|
最后修改于 2020-05-05

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。